제출 #675687

#제출 시각아이디문제언어결과실행 시간메모리
675687DenkataBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2075 ms503188 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; vector <int> v[100006]; int i,j,p,q,n,m,k,y,t; int Q; vector <pair <int,int>> best[100006]; const int crit = 320; int used[100006]; int dp[100006]; int covered[100006]; int dfs(int u) { if(covered[u]==Q+1) return dp[u]; covered[u]=Q+1; dp[u]=-1; if(used[u]!=Q+1)dp[u]=0; for(auto j:v[u]) { int val = dfs(j); if(val!=-1) dp[u]=max(dp[u],1+val); } return dp[u]; } 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...