Submission #1205712

#TimeUsernameProblemLanguageResultExecution timeMemory
1205712minhpkBitaro’s Party (JOI18_bitaro)C++20
0 / 100
24 ms48196 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int a,b,q; vector <int> z[1000005]; vector<pair<int,int>> lps[1000005]; int val[1000005]; int time1[100005]; int block; bool cmp(pair<int,int> a,pair<int,int> b){ return a.second>b.second; } int del[1000005]; bool vis[1000005]; int max1=-1; void dfs(int i,int dem){ if (del[i]!=q){ max1=max(max1,dem); } vis[i]=true; for (auto p:z[i]){ if (vis[p]){ continue; } dfs(p,dem+1); } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> a >> b >> q; block=321; for (int i=1;i<=b;i++){ int x,y; cin >> x >> y; z[y].push_back(x); } for (int i=1;i<=a;i++){ del[i]=1e16; vector <int> v; val[i]=0; time1[i]=i; v.push_back(i); for (auto p:z[i]){ for (auto p1:lps[p]){ if (time1[p1.first]!=i){ time1[p1.first]=i; val[p1.first]=p1.second+1; v.push_back(p1.first); }else{ val[p1.first]=max(val[p1.first],p1.second+1); } } } for (auto p:v){ lps[i].push_back({p,val[p]}); } sort(lps[i].begin(),lps[i].end(),cmp); int k=lps[i].size(); while (k>block){ lps[i].pop_back(); k--; } } // for (int i=1;i<=a;i++){ // cout << lps[i][0].second << " "; // } // cout << "\n"; while (q--){ int t,x; cin >> t >> x; for (int i=1;i<=x;i++){ int y; cin >> y; del[y]=q; } if (x>block-1){ for (int i=1;i<=a;i++){ vis[i]=false; } max1=-1; dfs(t,0); cout << max1 << "\n"; }else{ int ans=-1; for (auto p:lps[t]){ if (del[p.first]!=q){ ans=p.second; break; } } cout << ans << "\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...