IOI19 Split the Attractions

문제

https://oj.uz/problem/view/IOI19_split

문제 보기 - Split the Attractions (IOI19_split) :: oj.uz

연결된 무방향 그래프가 하나 주어졌을 때 정점들을 $A$, $B$, $C$ 세 개의 집합으로 분리해야 한다. 조건은 $A$, $B$, $C$의 각 집합의 크기는 이미 정해져 있고, 세 집합들 중 적어도 두개는 하나의 커넥티드 컴포넌트를 이루어야 한다.

($N<=100000$, $M<=200000$)

 

풀이

https://koosaga.com/236

이 문제는 여러 개의 아름다운 관찰들과 lemma들로 풀린다.

 

일반성을 잃지 않고, $a<=b<=c$라 하자.

Observation 1 : 해가 존재한다면 $A$, $B$만이 커넥티드 컴포넌트인 해도 존재한다.

이를 증명하기 위해서는 크기 $X$인 커넥티드 컴포넌트가 존재한다면 크기 $Y<X$인 커넥티드 컴포넌트도 존재함을 보이면 된다. 연결된 컴포넌트이기 때문에 아무런 스패닝 트리를 잡고, DFS preorder 순으로 생각하며 하나씩 집합에 집어 넣는다고 생각하면 어떠한 $Y<X$에 대해서도 해가 존재함을 알 수 있다. 따라서 이는 성립하고, 우리는 $A$, $B$에 대해서만 생각하자.

 

Observation 2 : "$A$, $B$크기의 두 커넥티드 컴포넌트를 잡는 것"과 "그래프를 정확히 두 집합으로 나누어 각 집합의 크기가 $A$이상, $B$이상 이 되도록 하는 것"은 동치이다.

위 1번 관찰에서 생각했던 것과 같이 하면 크기 A이상, B이상인 두 컴포넌트에서 크기 A, B인 집합을 뽑아내는 것은 가능하고, 거꾸로 만약 A, B인 두 컴포넌트를 잡았다면, A에서 BFS를 하여 최대한 선택하지 않는 정점들을 먹고, 나머지는 B에 배정되면 두 집합은 각각 커넥티드 컴포넌트이기 때문에 역도 성립하여 필요충분이다.

 

이제 위 두 관찰들로 인해 그래프를 정확히 두 개의 집합으로 쪼개고, 각 집합의 크기가 $A$, $B$이상이 되도록 하기만 하면 된다. 이것이 불가능하다면 원래 문제도 풀 수 없다.

 

Observation 3 : $a<=b<=c$에서 $a<=\frac{N}{3}$, $b<=\frac{N-a}{2}$

 

3번 관찰에서 Centroid 를 생각해볼 수 있다. 이 문제의 풀이의 핵심은 Centroid이다.

Centroid는 트리에서 그 점을 제거했을 때 남는 모든 컴포넌트의 크기 $\frac{N}{2}$이하가 되도록 하는 정점이다.

일반적인 그래프에서 문제를 풀지만, 임의의 스패닝 트리를 하나 잡고 생각하자.

 

 

Case 1

만약 Centroid를 제거한 뒤 남은 서브트리들 중 $A$크기 이상의 서브트리가 존재한다고 하자. 그렇다면 그 서브트리를 통째로 $A$ 집합에 배정하고, 나머지를 $B$에 주면 된다. 서브트리의 크기가 $\frac{N}{2}$이하이니, 그 서브트리를 제거하고 남은 부분의 크기는 $\frac{N}{2}$이상이다. $b<=\frac{N-a}{2}<=\frac{N}{2}$ 에서 이 컴포넌트는 $B$보다 크거나 같다.

 

Case 2

이제 남은 상황은 오직 Centroid를 제거하고 남은 모든 서브트리의 크기가 $A$미만이어서, 어느 서브트리를 통째로 주어도 해결하지 못하는 상황이다. 이 상황이 트리였다면 두 집합 중 적어도 하나는 센트로이드를 포함하기 때문에 한 집합은 서브트리 한 집합만을 먹어야 하는데, 모두 $A$미만이기 때문에, 답이 존재하지 않는다. 하지만 그래프에서 우리는 스패닝 트리에 포함되지 않은 간선들도 존재하기 때문에 아직 답이 존재하지 않는다고 말할 수는 없다.

센트로이드 기준으로 잘라지는 각 서브트리들을 한 컴포넌트라고 생각하면, 여러 개의 컴포넌트들로 쪼개져 있고, 스패닝 트리에 속하지 않는 간선들로 인해 이 컴포넌트들이 몇개가 묶여 있는 꼴이 될 것이다. 또한, 각 컴포넌트들의 사이즈는 $A$ 미만이다.

만약 그러한 엣지로 컴포넌트들을 다 묶고 나서도 최대 컴포넌트의 크기가 $A$이하라면, 위에서 이용한 것과 같은 논리로 그래프에서도 답이 존재하지 않는다. 이제 그것도 아닌 상황만 살펴보자.

다 묶었을 때 $A$이상이 되는 컴포넌트를 고르고, 다 묶지 말고 하나씩 컴포넌트를 추가해 나가 보자. 그리고 $A$를 넘기는 첫번째 순간이 오면 그 순간 멈추고, 나머지 (Centroid 포함) 은 모두 $B$에 넣어 주자. 이것이 과연 성립할까?

각 컴포넌트의 크기가 $a$ 미만임을 생각하면 $a$를 넘기는 순간에서의 그 컴포넌트의 크기는 $2a$미만이다. 그러면 남은 노드들의 총 수는 $N-2a$이하이고, 우리는 $b<=N-2a$임만 보이면 된다. 하지만 $\frac{N-a}{2}<=N-2a$가 성립하고, $b<=\frac{N-a}{2}$이니 $B$는 남은 컴포넌트에 무사히 들어간다는 것을 알 수 있다.

 

시간 복잡도 : $O(NlogN)$

 

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, ans[MAXN+10];
pii A[4];
vector<int> adj[MAXN+10], adj2[MAXN+10], adj3[MAXN+10];
	
int sz[MAXN+10], id[MAXN+10];

void getsz(int now, int bef)
{
	sz[now]=1;
	for(int nxt : adj2[now])
	{
		if(nxt==bef) continue;
		getsz(nxt, now);
		sz[now]+=sz[nxt];
	}
}

int getcen(int now, int bef, int S)
{
	for(int nxt : adj2[now])
	{
		if(nxt==bef) continue;
		if(sz[nxt]>S/2) return getcen(nxt, now, S);
	}
	return now;
}

void color(int now, int bef, int col, int &k)
{
	if(k<=0) return;
	ans[now]=col; k--;
	for(int nxt : adj2[now])
	{
		if(nxt==bef) continue;
		if(ans[nxt]) continue;
		color(nxt, now, col, k);
	}
}

void color2(int now, int bef, int root)
{
	id[now]=root;
	for(int nxt : adj2[now])
	{
		if(nxt==bef) continue;
		color2(nxt, now, root);
	}
}

bool vis[MAXN+10];
void dfs(int now)
{
	vis[now]=true;
	for(int nxt : adj[now])
	{
		if(vis[nxt]) continue;
		adj2[now].push_back(nxt);
		adj2[nxt].push_back(now);
		dfs(nxt);
	}
}

vector<int> V;
void dfs2(int now, int &k)
{
	vis[now]=true;
	k+=sz[now]; V.push_back(now);
	if(k>=A[1].first) return;
	for(int nxt : adj3[now])
	{
		if(vis[nxt]) continue;
		dfs2(nxt, k);
	}
}

void solve()
{
	int i, j;

	memset(vis, 0, sizeof(vis));
	dfs(1);
	getsz(1, 1);
	int cen=getcen(1, 1, N);
	getsz(cen, cen);

	for(int now : adj2[cen])
	{
		color2(now, cen, now);
		if(A[1].first<=sz[now])
		{
			int t=A[1].first;
			color(now, cen, A[1].second, t);
			t=A[2].first;
			color(cen, now, A[2].second, t);
			for(i=1; i<=N; i++) if(ans[i]==0) ans[i]=A[3].second;
			return;
		}
	}

	for(i=1; i<=N; i++)
	{
		int now=i;
		if(now==cen) continue;
		for(int nxt : adj[now])
		{
			if(nxt==cen) continue;
			if(id[now]==id[nxt]) continue;
			adj3[id[now]].push_back(id[nxt]);
		}
	}

	memset(vis, 0, sizeof(vis));
	for(int now : adj2[cen])
	{
		if(vis[now]) continue;
		int t=0;
		dfs2(now, t);
		if(t<A[1].first) continue;

		t=A[1].first;
		for(auto it : V) color(it, cen, A[1].second, t);
		color(cen, cen, A[2].second, A[2].first);
		for(i=1; i<=N; i++) if(ans[i]==0) ans[i]=A[3].second;
		return;
	}
}

vector<int> find_split(int _N, int _A, int _B, int _C, vector<int> _P, vector<int> _Q)
{
	int i, j;
	N=_N; A[1]=pii(_A, 1); A[2]=pii(_B, 2); A[3]=pii(_C, 3);
	for(i=0; i<_P.size(); i++)
	{
		int u=_P[i]+1, v=_Q[i]+1;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	sort(A+1, A+4);

	solve();

	vector<int> _ans(N);
	for(i=1; i<=N; i++) _ans[i-1]=ans[i];
	return _ans;
}