제출 #675695

#제출 시각아이디문제언어결과실행 시간메모리
675695DenkataBitaro’s Party (JOI18_bitaro)C++17
7 / 100
1006 ms524288 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; vector <long long> v[100006]; long long i,j,p,q,n,m,k,y,t; long long Q; vector <pair <long long,long long>> best[100006]; const long long crit = 150; long long used[100006]; long long dp[100006]; long long covered[100006]; long long dfs(long long 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]) { long long 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((long long)best[i].size()>crit) best[i].pop_back(); } } while(Q--) { long long 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<(long long)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...