Submission #1209874

#TimeUsernameProblemLanguageResultExecution timeMemory
1209874Younis_DwaiBitaro’s Party (JOI18_bitaro)C++20
0 / 100
2097 ms10568 KiB
#pragma GCC optimize("O3,unroll-loops,Ofast") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> #define endl "\n" #define F first #define S second #define pb push_back #define pf push_front #define popf pop_frot #define popb pop_back #define int long long #define in insert #define mid (l+r)/2 //register int cnt using namespace std; const int N=1e5+5; const int sqr=500; vector<int> adj[N]; int vis[N]; struct loin{ pair<int,int> b[501]; }; loin combine(loin &x , loin &y){ loin ret; int id1=1,id2=1,skip=0; while(id1+id2-2-skip<sqr){ //cout<<" @ "<<id1<<' '<<id2<<' '<<skip<<endl; if(id1<=sqr && vis[x.b[id1].S]==1){ ++id1; ++skip; continue ; } else if(id2<=sqr && vis[y.b[id2].S]==1){ ++id2; ++skip; continue ; } if(id2==sqr+1 || (y.b[id2].S==0 && x.b[id1].S!=0)){ ret.b[id1+id2-1]=x.b[id1]; if(x.b[id1].S!=0) vis[x.b[id1].S]=1; id1++; } else if(id1==sqr+1 || (x.b[id1].S==0 && y.b[id2].S!=0)){ ret.b[id1+id2-1].F=y.b[id2].F+1; ret.b[id1+id2-1].S=y.b[id2].S; if(y.b[id2].S!=0) vis[y.b[id2].S]=1; id2++; } else if(x.b[id1].F>=y.b[id2].F+1){ ret.b[id1+id2-1]=x.b[id1]; if(x.b[id1].S!=0) vis[x.b[id1].S]=1; id1++; } else{ ret.b[id1+id2-1].F=y.b[id2].F+1; ret.b[id1+id2-1].S=y.b[id2].S; if(y.b[id2].S!=0) vis[y.b[id2].S]=1; id2++; } //cout<<" @ "<<id1<<' '<<id2<<' '<<skip<<endl; } for(int i=1;i<=sqr;i++){ vis[x.b[i].S]=vis[y.b[i].S]=0; } //cout<<" @ "<<' '; for(int j=1;j<=sqr;j++){ if(ret.b[j].S==0) break ; //cout<<ret.b[j].F<<' '; } //cout<<endl; return ret; } int n,m,Q,busy[N],d[N]; loin best[N]; int32_t main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(nullptr); cin>>n>>m>>Q; for(int i=1;i<=n;i++){ for(int j=1;j<=sqr;j++){ best[i].b[j]={0,0}; } } for(int i=1;i<=m;i++){ int x,y;cin>>x>>y; adj[y].pb(x); } loin cur; for(int j=1;j<=sqr;j++) cur.b[j]={-1,0}; for(int i=1;i<=n;i++){ best[i].b[1]={0,i}; for(auto u : adj[i]){ //cout<<" # "<<i<<' '<<u<<endl; cur.b[1]={-1,u}; loin z=combine(best[u],cur); best[i]=combine(best[i],z); } } busy[0]=1; while(Q--){ int node,cnt;cin>>node>>cnt; vector<int> v; for(int i=1;i<=cnt;i++){ int x;cin>>x; v.pb(x); busy[x]=1; } if(cnt<sqr){ int ret=-1; for(int i=1;i<=sqr;i++){ if(busy[best[node].b[i].S]==0){ ret=max(ret,best[node].b[i].F); } } cout<<ret<<endl; } else{ queue<int> q; for(int i=1;i<=n;i++) d[i]=0; q.push(node); while(!q.empty()){ int node=q.front(); for(auto u : adj[node]){ if(d[u]<d[node]+1){ d[u]=1+d[node]; q.push(u); } } } int ret=-1; for(int i=1;i<=node;i++){ if(busy[i]) continue ; ret=max(ret,d[i]); } cout<<ret<<endl; } for(auto u : v){ busy[u]=0; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...