[IOI2014 Day1] Game 해법

여러 가지 다양한 해법이 있다고 생각한다.

$0$번 도시 부터 $N-1$번 도시까지 총 $N$개의 도시가 있다. 이 $N$개의 도시들을 단말 노드로 갖는 이진 트리를 만든다. 이 이진트리의 단말 노드의 개수는 정확히 $N$개이다. 이제 모든 $(i,j)$ 쌍 ($0 \leq i < j \leq N-1$)에 대하여 단말 노드 $i$와 단말 노드 $j$의 LCA(Lowest Common Ancestor, 최저 공통 조상)를 $k$라 했을 때, left[k]에 1을 더한다.

쿼리(질문)가 $(u,v)$으로 주어졌을 때, 단말 노드 $u$와 단말 노드 $v$의 LCA를 $w$라 했을 때, left[w] 값을 1 감소 시키고, 그 값이 0 이면, 값을 1 반환하고 감소한 뒤 그 값이 여전히 0 보다 크다면 0을 반환한다.

이런 일련의 알고리즘으로 질문에 대한 답을 하였을 때, 그래프가 연결 그래프임도 증명이 되고, 마지막 질문 전에는 그래프가 연결 그래프가 안됨이 증명된다.

처음 전처리로 이진 트리를 구성하고 모든 $(i,j)$ 쌍에 대한 LCA도 구해 놓는다. 이 때 걸리는 시간복잡도는 $O(N^2 lg N)$ 이다. 쿼리에 대해 답을 계산하는 시간복잡도는 $O(1)$ 이다. 따라서, 문제를 해결하기 위한 전체 시간복잡도는 $O(N^2 lg N)$ 이다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#include <queue> #include <algorithm> using namespace std;   #define sz(v) ((int)(v).size())   static int N,K,H[3333],par[3333][13],LCA[1501][1501],left[3333]; static queue <int> P,Q;   static int lca(int a,int b) {     int i;     if (H[a] < H[b]) swap(a,b);     for (i=0;i<13;i++) if ((H[a]-H[b])&(1<<i)) a = par[a][i];     if (a == b) return a;     for (i=13;i--;){         if (par[a][i] != par[b][i]) a = par[a][i], b = par[b][i];     }     return par[a][0]; }   void initialize(int n) {     int i,j,k;     N = K = n;     for (i=1;i<=N;i++) P.push(i), H[i] = 1e9;     while (sz(P) > 1){         while (!P.empty()){             int p = P.front(); P.pop();             if (P.empty()){                 par[p][0] = ++K;             }else{                 int q = P.front(); P.pop();                 par[p][0] = par[q][0] = ++K;             }             H[K] = H[p]-1;             Q.push(K);         }         P = Q; Q = queue<int>();     }     for (i=1;i<13;i++) for (j=1;j<=K;j++) par[j][i] = par[par[j][i-1]][i-1];     for (i=1;i<N;i++) for (j=i+1;j<=N;j++){         left[LCA[i][j]=lca(i,j)]++;     } }   int hasEdge(int u,int v) {     ++u; ++v;     if (u > v) swap(u,v);     if (!--left[LCA[u][v]]) return 1;     return 0; }