JOI 2013 - synchronization 문제 질문입니다.

  • kaizero
    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은 도저히 해법이 떠오르지 않네요..

    해법이나 조금의 힌트를 주시면 감사하겠습니다!


    11년 전
7개의 댓글이 있습니다.
  • 일루
    일루

    쉽지 않군요 ㅋㅋ 생각중입니다


    11년 전 link
  • wookayin
    wookayin

    Link-cut Tree 의 느낌이 나네요.. 요즘 일본 고딩들은 이런 어려운것도 푸나..


    11년 전 link
  • 샥후
    샥후

    트리가 정해져 있기 때문에, 간선이 최초로 이어질 때 양쪽 그룹의 정보는 항상 교집합이 없습니다. 그 이후에 끊어지고 다시 연결될 때는 가장 마지막으로 끊어진 시점의 정보가 교집합입니다.

    위의 특성을 이용해 모든 정보를 저장하지 않고 갯수만 저장하여 문제를 해결할 수 있습니다.

    시간복잡도는 각각 트리의 그룹을 저장하는 자료구조 (Link-cut Tree, etc..) 에 의해 결정됩니다.


    11년 전 link
  • iddaga
    iddaga
    • 루트Q 개씩 쿼리를 끊어서 처리하는 방식으로 트리의 그룹을 저장하시면 Link-cut Tree 를 쓰지 않으셔도 해결할 수 있습니다.

    11년 전 link
  • iddaga
    iddaga

    ㅋㅋ +를 앞에다 쓰면 저렇게 표시가 되네여


    11년 전 link
  • kaizero
    kaizero

    Link-cut Tree를 쓰지 않아도 해결이 가능하군요 ㄷㄷ 덧글 달아주신 모든 분들 감사합니다!


    11년 전 link
  • Kureyo
    Kureyo

    !! 아하 루트로 쪼개면 되는군요


    11년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.