제출 #1190292

#제출 시각아이디문제언어결과실행 시간메모리
1190292boclobanchatBitaro’s Party (JOI18_bitaro)C++20
100 / 100
1468 ms260664 KiB
#include<bits/stdc++.h> using namespace std; #define ii pair<int,int> #define fi first #define se second const int MAXN=1e5+5; const int sqr=320; vector<ii> vi[MAXN]; vector<int> ds[MAXN]; int dp[MAXN]; bool ck[MAXN]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m,q; cin>>n>>m>>q; while(m--) { int l,r; cin>>l>>r; ds[r].push_back(l); } for(int i=1;i<=n;i++) { vi[i].push_back({0,i}); for(auto v:ds[i]) { vector<ii> curr,a=vi[i],b; for(auto u:vi[v]) b.push_back({u.fi+1,u.se}); int l=0,r=0,sza=a.size(),szb=b.size(); for(int j=0;j<sqr&&(l<sza||r<szb);j++) { ii x={-1,-1},y={-1,-1}; while(l<sza&&ck[a[l].se]) l++; while(r<szb&&ck[b[r].se]) r++; if(l<sza) x=a[l]; if(r<szb) y=b[r]; if(x>y) l++,curr.push_back(x),ck[x.se]=true; else r++,curr.push_back(y),ck[y.se]=true; } for(auto v:curr) ck[v.se]=false; vi[i]=curr; } } while(q--) { int t,y; cin>>t>>y; if(y<sqr) { vector<int> vv; bool e=false; for(int i=1;i<=y;i++) { int res; cin>>res; ck[res]=true,vv.push_back(res); } for(auto v:vi[t]) if(!ck[v.se]) { cout<<v.fi<<"\n"; e=true; break; } if(!e) cout<<"-1\n"; for(auto v:vv) ck[v]=false; } else { for(int i=1;i<=n;i++) dp[i]=0; for(int i=1;i<=y;i++) { int res; cin>>res; dp[res]=-1e9; } for(int i=1;i<=n;i++) for(auto v:ds[i]) dp[i]=max(dp[i],dp[v]+1); if(dp[t]<0) cout<<"-1\n"; else cout<<dp[t]<<"\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...