Submission #1213613

#TimeUsernameProblemLanguageResultExecution timeMemory
1213613boss_zzBitaro’s Party (JOI18_bitaro)C++20
7 / 100
2094 ms15460 KiB
#include<bits/stdc++.h> #define rep(a,b,c) for(ll a=b;a<=c;++a) #define ll long long #define ff first #define ss second #define mp make_pair using namespace std; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const ll N=1e5+5,inf=1e18,B=300; ll n,m,q,dp[N]; vector<ll> adj_pos[N],adj_opp[N],tmp; vector<pll> T[N]; bitset<N> ban; void F(vector<pll> &T){ sort(T.begin(),T.end(),[](pll a,pll b){return a.ss>b.ss;}); if((ll)T.size()>B) T.resize(B); } void build(){ rep(i,1,n) T[i].push_back(mp(i,0)); rep(i,2,n){ for(ll j:adj_opp[i]) for(auto o:T[j]){ T[i].push_back(mp(o.ff,o.ss+1)); if((ll)T[i].size()>B) F(T[i]); } F(T[i]); } } ll SMALL(ll v){ for(auto o:T[v]) if(!ban[o.ff]) return o.ss; return -1; } ll BIG(ll v){ fill(dp+1,dp+n+1,-1); dp[v]=0; for(ll i=v-1;i>=1;--i){ for(ll j:adj_pos[i]){ if(dp[j]==-1) continue; dp[i]=max(dp[i],dp[j]+1); } } ll ans=-1; rep(i,1,v) if(!ban[i]) ans=max(ans,dp[i]); return ans; } signed main(){ ios::sync_with_stdio(0);cin.tie(0); cin>>n>>m>>q; rep(i,1,m){ ll u,v; cin>>u>>v; if(u>v) swap(u,v); adj_pos[u].push_back(v); adj_opp[v].push_back(u); } build(); while(q--){ ll v,k,x; cin>>v>>k; rep(i,1,k) cin>>x,tmp.push_back(x),ban[x]=1; if(k>=B) cout<<BIG(v)<<'\n'; else cout<<SMALL(v)<<'\n'; for(ll i:tmp) ban[i]=0; vector<ll>().swap(tmp); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...