제출 #771061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
771061		Mohammad_Parsa	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1116 ms	414436 KiB

bitaro

/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
typedef long long ll;

const int N=1e5+7,sq=300;
int n,m,q,vis[N],dp[N],b[N];
vector<int>cev[N];
vector<pair<int,int>>a[N],x;

void merge(int v,int u){
	x.clear();
	int s1=a[v].size(),s2=a[u].size(),i=0,j=0;
	pair<int,int>p,f;
	while(x.size()<sq && !(i==s1 && j==s2)){
		if(i==s1){
			p=a[u][j];j++;
			p.F++;
		}
		else if(j==s2){
			p=a[v][i];i++;
		}
		else{
			f=a[u][j];f.F++;
			if(f>a[v][i]){
				j++;p=f;
			}
			else{
				p=a[v][i];i++;
			}
		}
		if(!vis[p.S]){
			vis[p.S]=1;
			x.pb(p);
		}
	}
	for(auto y:x){
		vis[y.S]=0;
	}
	swap(a[v],x);
	return;
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	int u,v;
	for(int i=0;i<m;i++){
		cin>>u>>v;
		cev[v].pb(u);
	}
	for(int i=1;i<=n;i++){
		a[i].pb(mk(0,i));
		for(auto u:cev[i]){
			merge(i,u);
		}
	}
	while(q--){
		int t,y;
		cin>>t>>y;
		for(int i=0;i<y;i++){
			cin>>b[i];
			vis[b[i]]=1;
		}
		if(y>=sq){
			fill(dp,dp+N,-1e9);
			for(int i=1;i<=n;i++){
				if(!vis[i])dp[i]=0;
				for(auto u:cev[i]){
					dp[i]=max(dp[i],dp[u]+1);
				}
			}
			if(dp[t]<0)dp[t]=-1;
			cout<<dp[t]<<endl;
		}
		else{
			int ans=-1;
			for(auto c:a[t]){
				if(vis[c.S])continue;
				ans=c.F;
				break;
			}
			cout<<ans<<endl;
		}
		for(int i=0;i<y;i++){
			vis[b[i]]=0;
		}
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86