Submission #627115

#	Time	Username	Problem	Language	Result	Execution time	Memory
627115		codr0	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1420 ms	276764 KiB

bitaro

// Code by Parsa Eslami

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>

#define err(x) cerr<#x<<" : "<<x<<'\n'
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define pb push_back
#define bit(i,j) ((j>>i)&1)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define dmid int mid=(r+l)/2
#define lc 2*id
#define rc 2*id+1

using namespace std;
const int N=1e5+4;
const int SQ=340;
vector<int> adj[N];
vector<pii> vc[N];
int ind[N];
int dp[N];
bool mark[N];

	int32_t main(){
	iostream::sync_with_stdio(0); cin.tie(0);

	int n,m,q; cin>>n>>m>>q;
	FOR(i,1,m){
		int v,u; cin>>v>>u;
		adj[u].pb(v);
	}
	FOR(i,1,n){
		vector<pii> vc0;
		vc[i].pb({-1,i});
		while(SZ(vc0)<=SQ){
			pair<pii,int> mx={{-2,-1},0};
			for(int u:adj[i]) while(ind[u]<SZ(vc[u])&&mark[vc[u][ind[u]].S]) ind[u]++;
			if(ind[i]<SZ(vc[i])){
				pair<pii,int> O={vc[i][ind[i]],i};
				maxm(mx,O);
			}
			for(int u:adj[i]) if(ind[u]<SZ(vc[u])){
				pair<pii,int> O={vc[u][ind[u]],u};
				maxm(mx,O);
			}
			mx.F.F++;
			if(mx.F.F==-1) break;
			ind[mx.S]++;
			mark[mx.F.S]=1;
			vc0.pb(mx.F);
		}
		vc[i]=vc0;
		for(pii x0:vc[i]) mark[x0.S]=0;
		ind[i]=0;
		for(int u:adj[i]) ind[u]=0;
	}
	FOR(__,1,q){
		int v; cin>>v;
		vector<int> bad; int w; cin>>w;
		FOR(_,1,w){
			int x0; cin>>x0; bad.pb(x0);
			mark[x0]=1;
		}
		int ans=-1;
		if(w>=SQ){
			FOR(i,1,v-1) dp[i]=-1;
			dp[v]=0;
			FORR(i,v,1) if(dp[i]!=-1)
				for(int u:adj[i]) maxm(dp[u],dp[i]+1);
			FOR(i,1,v) if(!mark[i]) maxm(ans,dp[i]);
		}else{
			for(pii x0:vc[v]) if(!mark[x0.S]) maxm(ans,x0.F);
		}
		cout<<ans<<'\n';
		for(int w0:bad) mark[w0]=0;
	}

	return 0;
	}

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