IOI 2011 Day 1 Task 1 : Tropical Garden(열대 식물원)

일단 이 문제는 대충 짠 소스가 200줄이 넘는다 (...)

솔직히 너무 복잡한 것 같다.

일단, 모든 정점을 두 가지로 나눈다.

(이 작업이 꼭 필요하진 않지만 이렇게 안하면 아마 400줄쯤 됐던 것 같다... 디버깅도 힘들어서 포기함)

한 정점은 가장 아름다운 길로 가고, 한 정점은 두 번째로 아름다운 길로 간다.

그러고 나서는 각 간선을 '잘 생각해서' 연결한다(...)

그러니까, 첫 번째 정점에 연결해야 할지 두 번째 정점에 연결해야 할지를 잘 따지면서 연결하면 된다.

그러면 전체 그래프는 방향 그래프가 되고, 각 정점은 최대 한 개의 사이클에 포함되게 된다.

모든 방문되지 않은 정점에서 DFS를 돌면서, 이미 탐색한 정점 만나면 거꾸로 가면서 P까지의 거리를 기록해준다.

예를 들어 한 점에서 사이클 까지의 거리가 2, 사이클 크기가 5라고 하자.

사이클에 처음 닿는 점이 P라고 하자.

그러면 그 점에서 P까지는 2, 7, 12, 17, ... 만큼 가면 도착하게 된다.

따라서 P까지의 거리와 함께 사이클을 돌 경우 사이클의 크기도 기록한다.

(P가 사이클 밖에 있는 경우에는 사이클 밖에 있음을 표시해주자)

각 DFS마다 timestamp를 하나씩 가지도록 하면,

이미 방문된 정점을 만났을 때

1) 아까 DFS 하면서 찾았던 정점인가?

2) 지금 돌다가 만난 정점인가?

(1)의 경우, 그 정점에서 P까지의 거리가 있을 것이다.

이를 거꾸로 돌면서 방금까지 DFS돌았던 정점들에서 P까지의 거리를 기록해준다.

(2)의 경우, 사이클이다!

P가 사이클 안에 있을 경우, 적당히 계산해서 P까지의 거리를 조금씩 늘리면서 기록해준다.

모든 정점을 한 번씩만 방문하기 때문에 시간복잡도는 이다.

상수가 조금 크긴 하지만..(전체 DFS 코드가 100줄이다 100줄;;)

이후 x steps에 대한 쿼리가 들어온다고 하면,

각 점의 첫 번째 정점(가장 아름다운 길로 나가는 정점)에서 P까지의 거리와 사이클 크기(각각 d와 c라고 하자)에서,

x >= d && ((x-d)%c)==0 이면 정확히 x 걸음 가면 P에 도착함을 알 수 있다.

사이클이 없는 경우에는 x==d인지만 확인하면 된다.