IOI 2010 Saveit
관찰 1. 간선으로 이웃한 정점은 허브와의 거리가 최대 1 차이 난다. 관찰 2. 스패닝 트리를 만들면 모든 정점에서 허브 i까지의 거리를 N-1개의 -1에서 1 사이의 정수로 표현할 수 있다. i에서 i까지의 거리는 0이라고 알 수 있고, dfs를 통해 거리를 계산해 줄 수 있기 때문이다. 이를 통하면 최적의 전략은 스패닝 트리와 간선에 대한 정보를 보내주고, 그것을 통해서 계산하는 것임을 알 수 있다. 스패닝 트리는 각 정점의 부모를 저장하면 9990 비트로 보낼 수 있다. 거리는 이론상 999*36*log 3개의 비트로 나타낼 수 있고, 실제로는 5개의 정수를 그룹지은 뒤 이를 8개의 비트로 나타내어 보냈다. 이는 57600비트를 사용하고, 이를 통해 만점을 받을 수 있다. #include "gra..
ioi problems
2021. 9. 16. 21:07