JOISC18 Bitaro

문제

oj.uz/problem/view/JOI18_bitaro

문제 보기 - Bitaro’s Party (JOI18_bitaro) :: oj.uz

정점 개수 N, 간선 개수 M개의 DAG가 주어진다. 이 때, 다음과 같은 쿼리에 답해야 한다.

정점 v로 오는 경로들 중, 시작점이 u1, u2, ..., uk 중 하나인 경로들을 제외했을 때 최장경로의 길이룰 구하라.

$N<=100000$

$M<=200000$

$Q<=100000$

$\sum K_i<=100000$

 

풀이

Naive한 방법은 각 쿼리마다, 시작점으로 불가능한 정점들을 모두 체크해놓고, DP를 새로 돌리며 새로운 최장경로를 찾는 것이다. 각 쿼리에 $O(N+M)$의 시간이 들어, 전체 시간복잡도는 $O(Q(N+M))$이다.

 

일반적인 DAG에서의 최장경로의 길이는 dp를 통해 계산해줄 수 있다.

이와 같은 아이디어로, 만약 시작점이 막힌 정점이 몇개 없다면, 이를 K번째 최단경로를 구하는 문제로 바꾸어 해결할 수 있다.

 

만약 $K_i<=K$라면, 각 정점에서 시작점이 서로 다른 1~K+1번째 최장경로들의 길이를 구해놓는다면, 막힌 정점을 모두 제거하고도, 위에서 구한 경로들 중에 답이 존재하게 된다. 이를 계산하는데 드는 시간은 DP를 이용하면 $O((N+M)KlogK)$이다.

 

위에서 K가 작을 때 잘 동작하는 알고리즘을 발견하였고, K의 합의 상한이 정해져 있으므로, sqrt decomposition을 이용한다.

 

먼저 $K=\sqrt{100000}$에 대해서 위 K+1번째 최장경로 DP를 돌린다.

$K_i$가 $\sqrt{100000}$보다 작은 경우, 위에서 전처리한 값을 이용하여 답을 구한다.

$K_i$가 $\sqrt{100000}$보다 큰 경우, 그 개수가 $\sqrt{100000}$보다 작으니, Naive한 알고리즘을 이용하여 답을 구한다.

 

시간 복잡도 : $O(Q+(N+M)logN\sqrt{100000})$

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 2e5;
const int SQ = 100;
const int INF = 1e9;
 
int N, M, Q;
vector<int> adj[MAXN+10];
int ans[MAXN+10];
int dp[MAXN+10];
int val[MAXN+10];
 
struct Data
{
	int T, P;
	vector<int> V;
};
Data A[MAXN+10];
vector<int> P[MAXN+10];
 
vector<pii> dp2[MAXN+10];
bool chk[MAXN+10];
 
int main()
{
	memset(ans, -1, sizeof(ans));
	scanf("%d%d%d", &N, &M, &Q);
	for(int i=1; i<=M; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[v].push_back(u);
	}
	for(int i=1; i<=Q; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		A[i].T=a; A[i].P=i;
		while(b--)
		{
			int t;
			scanf("%d", &t);
			A[i].V.push_back(t);
		}
 
		if(A[i].V.size()>=SQ)
		{
			for(int j=1; j<=N; j++) dp[j]=0;
			for(auto it : A[i].V) dp[it]=-INF;
			for(int j=1; j<=N; j++) for(auto nxt : adj[j]) dp[j]=max(dp[j], dp[nxt]+1);
			if(dp[A[i].T]>=0) ans[i]=dp[A[i].T];
		}
		else P[A[i].T].push_back(i);
	}
 
	for(int now=1; now<=N; now++)
	{
		dp2[now].push_back({0, now});
		vector<int> V;
		for(auto nxt : adj[now])
		{
			for(auto it : dp2[nxt])
			{
				val[it.second]=max(val[it.second], it.first+1);
				V.push_back(it.second);
			}
		}
		
		for(auto it : V)
		{
			if(chk[it]) continue;
			chk[it]=true;
			dp2[now].push_back({val[it], it});
		}
		for(auto it : V) chk[it]=false;
		sort(dp2[now].begin(), dp2[now].end(), greater<pii>());
		while(dp2[now].size()>SQ) dp2[now].pop_back();
		for(auto it : V) val[it]=0;
 
		for(auto it : dp2[now]) chk[it.second]=false;
		for(auto it : P[now])
		{
			for(auto pt : A[it].V) chk[pt]=true;
			for(auto jt : dp2[now])
			{
				if(!chk[jt.second])
				{
					ans[it]=jt.first;
					break;
				}
			}
			for(auto pt : A[it].V) chk[pt]=false;
		}
	}
 
	for(int i=1; i<=Q; i++) printf("%d\n", ans[i]);
}