[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)$ 이다.

#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; }