JOI Co., Ltd.는 전 세계에 무려 N대의 서버를 두고 있습니다. 각 서버에는 중요한 정보의 일부가 저장되어 있고, 서로 다른 서버에는 서로 다른 정보가 저장되어 있습니다. JOI Co., Ltd.는 서버들끼리 정보를 공유하기 위해 서버들 사이에 정보를 양방향으로 교환할 수 있는 회선을 설치하고 있습니다. 정보들은 회선을 통해 여러 서버를 거쳐갈 수 있습니다.
각 서버는 고성능 동기화 시스템을 갖추고 있습니다. 두 서버가 서로 정보를 교환할 수 있는 상태이고, 서로 다른 정보를 가지고 있다면, 두 서버는 자동으로 서로의 정보를 공유합니다. 두 서버 A와 B 사이에 동기화가 이루어졌다면, A와 B가 가지고 있는 정보는 동기화 이전 A가 가지고 있던 정보와 B가 가지고 있던 정보의 합집합이 됩니다.
돈을 아끼기 위해, 회선은 N−1개만 설치됩니다. N−1개의 회선이 설치되고 나면, 임의의 두 서버 사이에 정보를 전달하는 경로는 유일할 것이고, 이 경로 상에서 거쳐 간 서버를 또 거쳐갈 일은 없습니다.
초기 (시간 0)에는 아무 회선도 지어지지 않은 상태입니다. 가끔씩 회선이 혹독한 환경 (사막, 바다 속, ..)에 설치되는 일도 있기 때문에, 회선이 이용 불가능할 때도 있습니다. 회선 하나가 작동하지 않으면, 복구될 때까지 정보들이 이 회선을 거쳐갈 수 없습니다.
시간 j (1≤j≤M)에는 반드시 회선 하나의 작동 여부가 바뀐다는 것이 알려져 있습니다. 우리는 시간 M+1에 Q개의 서버에 대해 들어 있는 서로 다른 정보의 개수를 구하고 싶습니다.
kaizero
문제 : http://cms.ioi-jp.org/open-2013/synchronization-en.pdf
JOI Co., Ltd.는 전 세계에 무려 N대의 서버를 두고 있습니다. 각 서버에는 중요한 정보의 일부가 저장되어 있고, 서로 다른 서버에는 서로 다른 정보가 저장되어 있습니다. JOI Co., Ltd.는 서버들끼리 정보를 공유하기 위해 서버들 사이에 정보를 양방향으로 교환할 수 있는 회선을 설치하고 있습니다. 정보들은 회선을 통해 여러 서버를 거쳐갈 수 있습니다.
각 서버는 고성능 동기화 시스템을 갖추고 있습니다. 두 서버가 서로 정보를 교환할 수 있는 상태이고, 서로 다른 정보를 가지고 있다면, 두 서버는 자동으로 서로의 정보를 공유합니다. 두 서버 A와 B 사이에 동기화가 이루어졌다면, A와 B가 가지고 있는 정보는 동기화 이전 A가 가지고 있던 정보와 B가 가지고 있던 정보의 합집합이 됩니다.
돈을 아끼기 위해, 회선은 N−1개만 설치됩니다. N−1개의 회선이 설치되고 나면, 임의의 두 서버 사이에 정보를 전달하는 경로는 유일할 것이고, 이 경로 상에서 거쳐 간 서버를 또 거쳐갈 일은 없습니다.
초기 (시간 0)에는 아무 회선도 지어지지 않은 상태입니다. 가끔씩 회선이 혹독한 환경 (사막, 바다 속, ..)에 설치되는 일도 있기 때문에, 회선이 이용 불가능할 때도 있습니다. 회선 하나가 작동하지 않으면, 복구될 때까지 정보들이 이 회선을 거쳐갈 수 없습니다.
시간 j (1≤j≤M)에는 반드시 회선 하나의 작동 여부가 바뀐다는 것이 알려져 있습니다. 우리는 시간 M+1에 Q개의 서버에 대해 들어 있는 서로 다른 정보의 개수를 구하고 싶습니다.
조건 : N<=200000, M<=100000, Q<=N
Subtask 1 : Q=1
Subtask 2 : 회선 i는 서버 i와 i+1 사이를 연결한다
Subtask 3 : 다른 조건 없음
제한시간 : 8초
Subtasks 1과 2는 풀 수 있는데 3은 도저히 해법이 떠오르지 않네요..
해법이나 조금의 힌트를 주시면 감사하겠습니다!
10년 전