Submission #543227

#TimeUsernameProblemLanguageResultExecution timeMemory
543227new_accBitaro’s Party (JOI18_bitaro)C++14
14 / 100
2083 ms283080 KiB
#include<bits/stdc++.h> #define fi first #define se second #define pitem item* using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; const int sq=350; const int N=1e5+10; pair<int,int> t[N][sq]; vi graf[N]; int ile[N],wsk[N],maxi[N]; bitset<N>byl,vis,vis2; int t2[N]; int n,m,q; vi tt; int f(int x){ vis2[x]=1; int ans=-1; for(int i=0;i<tt.size();i++){ int v=tt[i]; if(!vis2[v]) continue; for(auto u:graf[v]) maxi[u]=max(maxi[u],maxi[v]+1),vis2[u]=1; if(!byl[v]) ans=max(ans,maxi[v]); } for(int i=1;i<=n;i++) vis2[i]=0,maxi[i]=0; return ans; } void solve(){ cin>>n>>m>>q; for(int i=0;i<m;i++){ int a,b; cin>>a>>b; graf[b].push_back(a); ile[a]++; } vi curr; for(int i=1;i<=n;i++) if(ile[i]==0) curr.push_back(i); while(curr.size()){ int v=curr.back(); curr.pop_back(); tt.push_back(v); for(auto u:graf[v]){ ile[u]--; if(ile[u]==0) curr.push_back(u); } } int pier=sqrt(n); for(int i=tt.size()-1;i>=0;i--){ int v=tt[i]; for(auto u:graf[v]) wsk[u]=1; for(int j=1;j<=pier;j++){ int maxi1=0,maxi2=0; for(auto u:graf[v]){ while(wsk[u]<=pier and (byl[t[u][wsk[u]].fi] or !t[u][wsk[u]].fi)) wsk[u]++; if(t[u][wsk[u]].fi!=0 and t[u][wsk[u]].se+1>maxi1) maxi1=t[u][wsk[u]].se+1,maxi2=t[u][wsk[u]].fi; } if(maxi1==0){ t[v][j]={v,0}; break; } t[v][j]={maxi2,maxi1}; byl[maxi2]=1; } for(int j=1;j<=pier;j++) byl[t[v][j].fi]=0; } for(int i=1;i<=q;i++){ int x,il; cin>>x>>il; for(int j=1;j<=il;j++){ int a; cin>>a; t2[j]=a; byl[a]=1; } if(il<0){ int res=0; for(int j=1;j<=pier;j++){ if(byl[t[x][j].fi] or !t[x][j].fi) continue; res=t[x][j].se; break; } cout<<(res==0?-1:res)<<"\n"; }else cout<<f(x)<<"\n"; for(int j=1;j<=il;j++) byl[t2[j]]=0; } } int main(){ ios_base::sync_with_stdio(0),cin.tie(0); solve(); }

Compilation message (stderr)

bitaro.cpp: In function 'int f(int)':
bitaro.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0;i<tt.size();i++){
      |              ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...