[IOI2012 Day2] City 해법

문제 ↓

city.pdf

상당히 까다로워 보이는 문제다. 대회 당시 만점자가 많지 않지만 매우 어려운 문제에 속하진 않는다.

문제는 2차원으로 되어 있지만, 1차원인 경우 부터 먼저 생각해보자. 1차원인 경우 각 셀들이 모두 연결되어 있어야하므로, 셀들이 일직선으로 연결되어있는 선분 하나만 존재할 것이다. 이 때 각 셀 쌍들이 이동하는 거리는 $|X_i-X_j|$ 이다. 이런 셀들이 N개 있을 때 O(N lg N) 정렬 후, O(N) 만에 각 셀 쌍들의 거리 합을 구해줄 수 있다.

전체 해법 설명에 앞서, 서브태스크 3 푸는 법을 먼저 소개하겠다. 서브태스크 3에 있는 조건들이라면 각 셀 쌍들의 이동 거리는 1차원일 때와 비슷하게 $|X_i-X_j|+|Y_i-Y_j|$ 이다. 이때 x 좌표의 거리와 y 좌표의 거리를 독립적으로 생각할 수 있다. 따라서 1차원에 $X_i$ 들만 있다고 가정했을 때 거리 합과 1차원에 $Y_i$ 들만 있다고 가정했을 때 거리합을 구하면 답이 된다.

이제 본격적으로 만점을 받을 수 있는 해법에 대해 설명하겠다. 우선, 문제의 조건을 다시 살펴보자. 모든 비어 있지 않은 셀들은 서로 연결되어 있고, 모든 비어있는 셀들은 서로 연결되어 있다. 즉, 구멍이 없다. 비어있지 않은 셀들을 1xC 꼴로 토막을 내자. (그림에서 수평선 마다 칼을 내려찍어 토막을 냈다고 보자). 각 한 토막을 그래프의 노드로 보고 토막이 연결되어 있으면 간선으로 연결해줘서 그래프를 구성하자. 문제의 조건에 따라 그려지는 그래프는 싸이클이 없고 모든 노드가 연결되어 있으므로 트리다. 이 트리를 이용하여, $|Y_i-Y_j|$ 들의 합을 구할 수 있다. $|X_i-X_j|$ 들의 합을 구할 때에는 각 셀들의 x좌표와 y좌표를 뒤바꿔 같은 일련의 작업을 해주면 코딩하기 편하다.

#include <vector> #include <algorithm> using namespace std; #define MAXN 100005 #define pb push_back #define sz(v) ((int)(v).size()) #define connect(a,b) con[a].pb(b),con[b].pb(a) typedef long long lld; static const int MOD = 1e9; static int N,M,ans; static vector<int> con[MAXN]; static struct Z{ int x,y; bool operator < (const Z &ot)const{ return y!=ot.y?y<ot.y:x<ot.x; } } A[MAXN]; static struct NODE{ int y,x1,x2; } T[MAXN]; int dfs(int n,int par) { int size=T[n].x2-T[n].x1+1,i,k; for (i=sz(con[n]);i--;){ k = con[n][i]; if (par == k) continue; size += dfs(k,n); } ans = (ans+(lld)size*(N-size))%MOD; return size; } void proc() { int i,j,s,e; sort(A+1,A+N+1); M = 0; for (i=j=1;i<=N;i++){ if (i == N || A[i].y != A[i+1].y || A[i].y == A[i+1].y && A[i].x+1 < A[i+1].x){ T[++M].y = A[i].y; T[M].x1 = A[j].x; T[M].x2 = A[i].x; j = i+1; } } for (i=1;i<=M;i++) con[i].clear(); for (i=1,s=e=2;i<=M;i++){ while (e <= M && (T[e].y <= T[i].y || T[e].y == T[i].y+1 && T[e].x1 <= T[i].x2)) e++; while (s <= M && (T[s].y <= T[i].y || T[s].y == T[i].y+1 && T[s].x2 < T[i].x1)) s++; for (j=s;j<e;j++) connect(i,j); } dfs(1,0); } int DistanceSum(int n, int *x, int *y) { int i; N = n; for (i=1;i<=N;i++) A[i].x = x[i-1], A[i].y = y[i-1]; proc(); for (i=1;i<=N;i++) swap(A[i].x,A[i].y); proc(); return ans; }