Submission #1209887

#TimeUsernameProblemLanguageResultExecution timeMemory
1209887Younis_DwaiBitaro’s Party (JOI18_bitaro)C++20
0 / 100
2093 ms5448 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=100; vector<int> adj[N]; int n,m,Q,busy[N],d[N],vis[N],largest[N]; vector<pair<int,int>> 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<=m;i++){ int x,y;cin>>x>>y; adj[y].pb(x); } for(int i=1;i<=n;i++){ best[i].pb({0,i}); vector<int> reach; for(auto u : adj[i]){ for(auto[dis , from] : best[u]){ if(vis[from]==0){ reach.pb(from); largest[from]=1+dis; vis[from]=1; } else{ largest[from]=max(1+dis,largest[from]); } } } for(auto u : reach){ best[i].pb({largest[u],u}); largest[u]=-1; vis[u]=0; } sort(best[i].rbegin(),best[i].rend()); while(best[i].size()>sqr) best[i].pop_back(); } 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(auto u : best[node]){ if(busy[u.S]==0){ ret=u.F; break ; } } 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...