hyper1423   8달 전

지문이 좀 이상해요...

1. 문제의 예제 입력이 좀 헷갈리게 나와 있는데, 이 문제는 한 번의 입력에 여러 테스트 케이스가 들어올 수 있습니다. EOF를 만날 때까지 모든 테스트 케이스를 읽고 답해야 합니다.

2. 문제의 지문에 나온 조건인 "Two towns are connected if they have been directly connected or interconnected through some other connected towns at some moment in time."이 굉장히 중요합니다. d 쿼리가 주어지면 자신과 직접적으로 연결된 도시는 끊기지만, 자신을 통해서 연결된 다른 도시들의 연결은 끊기지 않습니다. 예를 들어, 1-2를 연결하고 2-3을 연결한 뒤에 2를 끊는다면, 1-2와 2-3은 끊기지만 1-3은 끊기지 않습니다. (1-2-3으로 연결되었던 시점이 존재하기 때문)

3. 문제에 쿼리가 최대 몇 개 주어지는지 나와있지 않은데, 직접 SEERC 2008의 데이터를 찾아본 결과 한 테스트 케이스당 최대 35000개 정도가 입력됩니다. $ O(N^2) $ 이상만 아니라면 돈다고 보시면 될 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.