Submission #1151090

#TimeUsernameProblemLanguageResultExecution timeMemory
1151090adkjtBitaro’s Party (JOI18_bitaro)C++20
14 / 100
1978 ms418100 KiB
#include<bits/stdc++.h> using namespace std; vector<int> g[111111],a[111111]; int mx[111111],dis[111111]; vector<pair<int,int>> now[111111]; int closed[111111]; int main() { int n,m,q;cin>>n>>m>>q; for(int i=1;i<=m;i++) { int u,v;cin>>u>>v; g[v].push_back(u); a[u].push_back(v); } memset(mx,-1,sizeof mx); for(int i=1;i<=n;i++) { now[i].push_back({0,i}); vector<int> use; for(auto x:g[i]) { for(auto xx: now[x]) { if(mx[xx.second]==-1) { mx[xx.second]=xx.first+1; use.push_back(xx.second); } else mx[xx.second]=max(mx[xx.second],xx.first+1); } } for(auto x:use) { now[i].push_back({mx[x],x}); mx[x]=-1; } sort(now[i].begin(),now[i].end()); reverse(now[i].begin(),now[i].end()); while(now[i].size()>sqrt(n)) now[i].pop_back(); } while(q--) { int T,Y;cin>>T>>Y; for(int i=1;i<=n;i++) closed[i]=0; for(int i=1;i<=Y;i++) { int x;cin>>x; closed[x]=1; } int sq=sqrt(n); if(Y>sq) { int ans=-1; for(int i=1;i<=n;i++) dis[i]=INT_MIN; dis[T]=0; for(int i=T;i>0;i--) { for(auto x:a[i]) { dis[i]=max(dis[i],dis[x]+1); } if(closed[i]) continue; ans=max(ans,dis[i]); } cout<<ans<<'\n'; } else { int ch=0; for(auto x:now[T]) { if(!closed[x.second]) { cout<<x.first<<'\n'; ch=1; break; } } if(!ch) cout<<-1<<'\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...