Submission #856650

#TimeUsernameProblemLanguageResultExecution timeMemory
856650GoldLightBitaro’s Party (JOI18_bitaro)C++17
0 / 100
0 ms344 KiB
#include <bits/stdc++.h> using namespace std; void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);} const int SQR=300; int main(){ fast(); int n, m, q; cin>>n>>m>>q; vector<int> v[n+1]; for(int i=1; i<=m; i++){ int x, y; cin>>x>>y; v[y].push_back(x); } vector<pair<int,int>> l[n+1]; //longest paths vector<int> dp(n+1), vis(n+1), block(n+1), dist(n+1), st; for(int i=1; i<=n; i++){ l[i].push_back({0, i}); for(auto j:v[i]){ for(auto [d, x]:l[j]){ if(vis[x]==i){ dist[x]=max(dist[x], d+1); } else{ dist[x]=d+1; vis[x]=i; st.push_back(x); } } } while(!st.empty()){ int u=st.back(); st.pop_back(); l[i].push_back({dist[u], u}); } sort(l[i].begin(), l[i].end(), greater<pair<int,int>>()); if((int)l[i].size()>SQR) l[i].erase(l[i].begin()+SQR, l[i].end()); } while(q--){ int t, y; cin>>t>>y; for(int i=1; i<=y; i++){ int x; cin>>x; block[x]=q; } if(y<SQR){ int ans=-1; for(auto [d, x]:l[t]){ if(block[x]!=q){ ans=d; break; } } cout<<ans<<'\n'; } else{ fill(dp.begin(), dp.end(), -1); for(int i=1; i<=n; i++){ if(block[i]!=q){ dp[i]=0; for(auto j:v[i]){ if(dp[j]!=-1) dp[i]=max(dp[i], dp[j]+1); } } } cout<<dp[t]<<'\n'; } } } /* const int N=1e6, SQR=1e3; int l[N+1], r[N+1], id[N+1]; bool cmp(int x, int y){ if(l[x]/SQR!=l[y]/SQR) return l[x]/SQR<l[y]/SQR; if((l[x]/SQR)&1) return r[x]<r[y]; return r[x]>r[y]; } int main(){ fast(); int n; cin>>n; for(int i=1; i<=n; i++){ cin>>l[i]>>r[i]; id[i]=i; } sort(id+1, id+n+1, cmp); // for(int i=1; i<=n; i++){ // cout<<l[id[i]]<<' '<<r[id[i]]<<'\n'; // } // int ans=0; // for(int i=2; i<=n; i++){ // int j=id[i], k=id[i-1]; // ans+=abs(l[j]-l[k])+abs(r[j]-r[k]); // } // cout<<ans; for(int i=1; i<=n; i++) cout<<id[i]<<' '; } */ /* const int N=2e5, SQR=300; int l[N+1], r[N+1], id[N+1]; bool cmp(int x, int y){ if(l[x]/SQR!=l[y]/SQR) return l[x]/SQR<l[y]/SQR; return r[x]<r[y]; } int now, a[N+1]; map<int,int> mp; void add(int x){ mp[a[x]]++; if(mp[a[x]]==1) now++; } void del(int x){ mp[a[x]]--; if(mp[a[x]]==0) now--; } int main(){ fast(); int n, q; cin>>n>>q; for(int i=1; i<=n; i++) cin>>a[i]; for(int i=1; i<=q; i++){ cin>>l[i]>>r[i]; id[i]=i; } sort(id+1, id+q+1); int ki=1, ka=0, ans[q+1]; for(int i=1; i<=q; i++){ int j=id[i]; while(ki>l[j]){ ki--; add(ki); } while(ka<r[j]){ ka++; add(ka); } while(ki<l[j]){ del(ki); ki++; } while(ka>r[j]){ del(ka); ka--; } ans[j]=now; } for(int i=1; i<=q; i++) cout<<ans[i]<<'\n'; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...