APIO20 Swap

문제

oj.uz/problem/view/APIO20_swap

문제 보기 - 자매 도시 (APIO20_swap) :: oj.uz

정점 개수 N, 간선 개수 M개의 연결 무방향 그래프가 주어질 때, 쿼리로 두 정점 X, Y가 주어진다. 이 때, 한 명은 X에서 Y로, 한 명은 Y에서 X로 이동한다. 이때 두 명이 만나서는 안되고, 한 간선을 가다가 중간에 돌아가는 등의 일은 할 수 없다. 이 때 두 사람이 이용하는 간선들의 가중치의 최댓값을 최소화한 값을 출력하자.

$N<=100000$

$M<=200000$

$Q<=200000$

 

풀이

Observation 1 : 두 사람 X, Y가 서로 도달 가능한 정점이기 위한 필요충분조건은 다음과 같다.

X, Y가 하나의 컴포넌트 C에 있으며, 

1. C에 degree가 3 이상인 정점이 존재한다.

2. C의 모든 정점들이 하나의 사이클로 묶여 있다.

1의 경우, degree가 3 이상인 정점 w가 존재한다면, X에서 w로 이동한 후, w에서 X, Y로 가는 경로가 아닌, 다른 정점 Z로 이동한다. 이후 Y가 w를 통해서 X로 동한 후, Z에 있던 X가 Y로 이동한다.

2의 경우 사이클일 때 자명하게 성립한다.

1, 2가 모두 아니라면, degree가 모두 2 이하이며, 모두 2이면 안되기 때문에, 가능한 것은 일직선 구조인 트리밖에 없으며, 이 때 불가능함은 자명하다.

 

따라서 위 조건을 크루스칼 알고리즘과 같이 가중치가 작은 간선부터 하나씩 추가해주며 해당 컴포넌트의 max degree, 간선의 개수, 노드의 개수를 관리하면 각 쿼리당 $O(M)$에 풀어, 전체 $O(MQ)$에 해결할 수 있다.

 

Observation 2 : 어떠한 컴포넌트가 어떤 순간에 위 조건을 만족하는 컴포넌트가 되었다면, 이 컴포넌트에 간선이 추가되어도 조건을 만족한다.

사이클에 간선이 추가된다면, 그 순간 그 간선의 degree가 3이 되므로 조건을 만족하고, degree가 3인 정점이 생긴 이후부터는 항상 조건을 만족한다.

 

따라서, 한 번의 Union Find 과정을 통하여 각 정점이 처음으로 조건을 만족하는 컴포넌트가 되는 순간을 찾아보자. 이를 위해, 각 컴포넌트의 정점들을 별도의 배열에 담아 큰거 작은거를 통하여 합쳐준다.

 

마지막으로, X, Y가 같은 컴포넌트에 있어야 한다는 조건을 생각하자. 이는 전체적인 그래프의 MST를 추출한 후, MST에서 두 정점 사이의 최대 가중치를 구하면 되고, 단순히 sparse table을 이용하면 해결할 수 있다.

 

시간 복잡도 : $O(Q+MlogM)$

 

#include "swap.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;
const int MAXM = 2e5;
 
struct Edge
{
	int u, v, w;
};
 
int N, M;
vector<pii> adj[MAXN+10];
Edge E[MAXM+10];
 
int deg[MAXN+10];
int par[MAXN+10], maxd[MAXN+10], sz[MAXN+10], ecnt[MAXN+10];
vector<pii> adj2[MAXN+10];
int T[MAXN+10];
 
int Find(int x)
{
	if(x==par[x]) return x;
	return Find(par[x]);
}
 
vector<int> V[MAXN+10];
 
void Union(int x, int y)
{
	x=Find(x); y=Find(y);
	if(x==y) return;
	if(sz[x]>sz[y]) swap(x, y);
	for(auto it : V[x]) V[y].push_back(it);
	V[x].clear();
	par[x]=y;
	maxd[y]=max(maxd[y], maxd[x]);
	sz[y]+=sz[x];
	ecnt[y]+=ecnt[x];
}
 
int ppar[MAXN+10][30], dep[MAXN+10], spa[MAXN+10][30];
 
void dfs(int now, int bef, int d, int val)
{
	dep[now]=d;
	ppar[now][0]=bef;
	spa[now][0]=val;
	for(auto nxt : adj2[now])
	{
		if(nxt.first==bef) continue;
		dfs(nxt.first, now, d+1, nxt.second);
	}
}
 
int maxdist(int u, int v)
{
	int ans=0;
	if(dep[u]>dep[v]) swap(u, v);
	for(int i=20; i>=0; i--) if(dep[ppar[v][i]]>=dep[u])
	{
		ans=max(ans, spa[v][i]);
		v=ppar[v][i];
	}
	if(u==v) return ans;
	for(int i=20; i>=0; i--) if(ppar[u][i]!=ppar[v][i])
	{
		ans=max(ans, spa[u][i]);
		ans=max(ans, spa[v][i]);
		u=ppar[u][i]; v=ppar[v][i];
	}
	ans=max(ans, spa[u][0]);
	ans=max(ans, spa[v][0]);
	return ans;
}
 
 
void init(int _N, int _M, vector<int> _U, vector<int> _V, vector<int> _W)
{
	N=_N; M=_M; 
	for(int i=0; i<M; i++)
	{
		int u=_U[i]+1, v=_V[i]+1, w=_W[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		E[i+1]={u, v, w};
	}
 
	sort(E+1, E+M+1, [&](const Edge &p, const Edge &q) { return p.w<q.w; });
 
	for(int i=1; i<=N; i++)
	{
		deg[i]=0;
		maxd[i]=0;
		par[i]=i;
		sz[i]=1; ecnt[i]=0;
		T[i]=1e9;
		V[i].push_back(i);
	}
 
	for(int i=1; i<=M; i++)
	{
		int u=E[i].u, v=E[i].v, w=E[i].w;
		deg[u]++; deg[v]++;
		if(Find(u)!=Find(v))
		{
			//printf("%d %d %d\n", u, v, w);
			adj2[u].push_back({v, w});
			adj2[v].push_back({u, w});
			Union(u, v);
		}
 
		ecnt[Find(u)]++;
		maxd[Find(u)]=max(maxd[Find(u)], max(deg[u], deg[v]));
 
		if(maxd[Find(u)]>=3 || (maxd[Find(u)]==2 && ecnt[Find(u)]==sz[Find(u)]))
		{
			for(auto it : V[Find(u)]) T[it]=E[i].w;
			V[Find(u)].clear();
		}
		//if(Find(X)==Find(Y) && maxd[Find(X)]==2 && ecnt[Find(X)]==sz[Find(X)]) { ans=E[i].w; break; }
	}
	dfs(1, 1, 1, 0);
 
	for(int i=1; i<=20; i++) for(int j=1; j<=N; j++)
	{
		ppar[j][i]=ppar[ppar[j][i-1]][i-1];
		spa[j][i]=max(spa[j][i-1], spa[ppar[j][i-1]][i-1]);
	}
 
	//for(int i=1; i<=N; i++) printf("T %d : %d\n", i, T[i]);
}
 
int X, Y;
 
int getMinimumFuelCapacity(int _X, int _Y)
{
	X=_X+1; Y=_Y+1;
 
	int ans=maxdist(X, Y);
	ans=max(ans, T[X]);
	ans=max(ans, T[Y]);
	if(ans>=1e9) ans=-1;
	return ans;
}