Submission #389808

#	Time	Username	Problem	Language	Result	Execution time	Memory
389808		nathanlee726	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1995 ms	453004 KiB

bitaro

//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
//#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
vector<int> g[100010],rg[100010],topo,rtopo;
vector<pair<pii,vector<int> > > qt1,qt2;
int n,b,d[100010],o[100010],y,in[100010],rin[100010];
vector<vector<pii> >dp(100010,vector<pii>(350,{0,0}));
bool vis[100010],used[100010];
void bfs(int x){
	F(n)d[i]=-1;
	queue<int> q;
	q.push(x);
	d[x]=0;
	int p0=0;
	while(rtopo[p0]!=x)p0++;
	while(p0<n){
		int p=rtopo[p0];
		if(d[p]!=-1){
			for(int u:rg[p]){
				d[u]=max(d[u],d[p]+1);
			}
		}
		p0++;
	}
}

signed main(){
	IOS();
	int m,q;
	cin>>n>>m>>q;
	b=sqrt(n);
	F(m){
		int x,y;
		cin>>x>>y;
		--x,--y;
		g[x].pb(y);
		rg[y].pb(x);
		in[y]++; 
		rin[x]++;
	}
	F(q){
		int x,y;
		cin>>x>>y;
		--x;
		vector<int> tv;
		Fi(j,y){
			int tx;
			cin>>tx;
			--tx;
			tv.pb(tx);
		}
		if(y>b)qt1.pb({{x,i},tv});
		else qt2.pb({{x,i},tv}); 
	}
	queue<int> qu;
	F(n){
		if(in[i]==0){
			qu.push(i);
		}
	}
	while(!qu.empty()){
		int p=qu.front();qu.pop();
		topo.pb(p);
		for(int u:g[p]){
			in[u]--;
			if(in[u]==0)qu.push(u);
		}
	}
	while(!qu.empty())qu.pop();
	F(n){
		if(rin[i]==0){
			qu.push(i);
		}
	}
	while(!qu.empty()){
		int p=qu.front();qu.pop();
		rtopo.pb(p);
		for(int u:rg[p]){
			rin[u]--;
			if(rin[u]==0)qu.push(u);
		}
	}
	for(auto node:qt1){
		bfs(node.X.X);
		for(int i:node.Y)d[i]=-1;
		int ans=-1;
		F(n)ans=max(ans,d[i]);
		o[node.X.Y]=ans;  
	}
	
	memres(used);
	for(int p:topo){
		vector<pii> v,tv;
		bug(p,sz(rg[p]));
		for(int u:rg[p]){
			int p0=0,p1=0;
			while(p0<sz(v)&&p1<sz(dp[u])&&sz(tv)<b+1){
				if(v[p0].X>dp[u][p1].X+1){
					if(!used[v[p0].Y]){
						used[v[p0].Y]=1;
						tv.pb({v[p0].X,v[p0].Y});
					}
					p0++;	
				}
				else{
					if(!used[dp[u][p1].Y]){
						used[dp[u][p1].Y]=1;
						tv.pb({dp[u][p1].X+1,dp[u][p1].Y});
					}
					p1++;
				}
			}
			if(sz(tv)<b+1){
				while(p0<sz(v)&&sz(tv)<b+1){
					if(!used[v[p0].Y]){
						used[v[p0].Y]=1;
						tv.pb({v[p0].X,v[p0].Y});
					}
					p0++;
				}
				while(p1<sz(dp[u])&&sz(tv)<b+1){
					if(!used[dp[u][p1].Y]){
						used[dp[u][p1].Y]=1;
						tv.pb({dp[u][p1].X+1,dp[u][p1].Y});
					}
					p1++;
				}
			}
			swap(tv,v);
			for(pii pi:v){
				used[pi.Y]=0;
			}
			tv.clear();
		}
		if(sz(v)<b+1){
			v.pb({0,p});
		}
		F(sz(v))bug(v[i].X,v[i].Y);
		swap(dp[p],v);
	}
	for(auto node:qt2){
		int ans=-1;
		for(int i:node.Y)used[i]=1;
		for(pii pi:dp[node.X.X]){
			if(!used[pi.Y]){
				ans=pi.X;
				break;
			}
		}
		for(int i:node.Y)used[i]=0;
		o[node.X.Y]=ans;
	}
	F(q)cout<<o[i]<<endl;
	return 0;
}

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