Submission #675697

#TimeUsernameProblemLanguageResultExecution timeMemory
675697DenkataBitaro’s Party (JOI18_bitaro)C++17
14 / 100
1231 ms380440 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; vector <int> v[200006]; int i,j,p,q,n,m,k,y,t; int Q; vector <pair <int,int>> best[200006]; const int crit = 150; int used[200006]; int dp[200006]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m>>Q; for(i=1; i<=m; i++) { cin>>p>>q; v[q].push_back(p); } for(i=1; i<=n; i++) { for(auto j:v[i]) { best[i].push_back({-1,j}); for(auto k:best[j]) best[i].push_back({k.first-1,k.second}); } if(!best[i].empty()) { sort(best[i].begin(),best[i].end()); while((int)best[i].size()>crit) best[i].pop_back(); } } while(Q--) { int party; cin>>party; cin>>y; for(i=1; i<=y; i++) { cin>>t; used[t]=Q+1; } bool fl=0; if(!best[party].empty()) { for(i=0; i<(int)best[party].size(); i++) { if(used[best[party][i].second]!=Q+1) { cout<<-best[party][i].first<<endl; fl=1; break; } } } if(fl)continue; if(y<crit) { if(used[party]==Q+1) cout<<-1<<endl; else cout<<0<<endl; continue; } ///bruteforce for(i=1;i<=party;i++) { if(used[i]==Q+1) dp[i]=-1; else dp[i]=0; for(auto j:v[i]) { if(dp[j]!=-1) dp[i]=max(dp[i],dp[j]+1); } } cout<<dp[party]<<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...