Submission #890177

#TimeUsernameProblemLanguageResultExecution timeMemory
890177LeVanThucBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2081 ms102288 KiB
#include<bits/stdc++.h> using namespace std; #define ll int #define fi first #define se second #define p(x,y) pair<ll,ll>(x,y) #define BIT(i,x) ((x>>i)&1) #define MASK(x) (1<<x) #define ld long double #define __builtin_popcount __builtin_popcountll #define pll pair<ll,ll> template<class T1,class T2> bool maximize(T1 &x,T2 y) { if(x<y) { x=y; return 1; } return 0; } template<class T1,class T2> bool minimize(T1 &x,T2 y) { if(y<x) { x=y; return 1; } return 0; } const ll M=1e9+7; template <class T1,class T2> void add(T1 &x,T2 y) { x+=y; if(x>=M) x-=M; } template <class T1,class T2> void sub(T1 &x, T2 y) { x-=y; if(x<0) x+=M; } void online() { std::ios_base::sync_with_stdio(0); cin.tie(0); #ifdef thuc freopen("input.inp","r",stdin); freopen("output.out","w",stdout); #else #endif // thuc } const ll N=2e5+10; ll vs[N],f[N],ban[N],n,m,q,src; vector<ll> gr[N],rgr[N]; ll solve1(ll u) { if(vs[u]) return f[u]; vs[u]=1; f[u]=-1e9; if(u==src) return f[u]=0; for(auto v:gr[u]) { maximize(f[u],solve1(v)+1); maximize(f[u],solve1(v)+1); } return f[u]; } ll tr(ll u,ll y) { src=u; for(int i=1; i<=n; i++) { vs[i]=0; } vector<ll> vt; for(int i=1; i<=y; i++) { ll x; cin>>x; ban[x]=1; vt.push_back(x); } ll ans=-1; for(int i=1; i<=n; i++) { if(!ban[i])maximize(ans,solve1(i)); } for(auto v:vt) ban[v]=0; return ans; } bool sub2() { ll t,y; cin>>t>>y; cout<<tr(t,y); return 0; } map<ll,ll> Map[N]; vector<pll> bt[N]; void dfs(ll u,ll d,ll src) { bool flag=0,flag1=0; for(int i=0; i<bt[u].size(); i++) { if(bt[u][i].se==src) { flag1=1; if(maximize(bt[u][i].fi,d)) { while(i>0&&bt[u][i].fi>bt[u][i-1].fi) swap(bt[u][i],bt[u][i-1]),i--; } break; } } if(!flag1) { if(bt[u].size()<200) { flag=1; bt[u].push_back(p(d,src)); ll i=bt[u].size()-1; while(i>0&&bt[u][i].fi>bt[u][i-1].fi) swap(bt[u][i],bt[u][i-1]),i--; } else { if(bt[u].back().fi<d) { flag=1; bt[u].back()=p(d,src); ll i=bt[u].size()-1; while(i>0&&bt[u][i].fi>bt[u][i-1].fi) swap(bt[u][i],bt[u][i-1]),i--; } } } if(flag) for(auto v:gr[u]) { dfs(v,d+1,src); } } ll tr2(ll u,ll y) { vector<ll> vt; for(int i=1; i<=y; i++) { ll x; cin>>x; vt.push_back(x); ban[x]=1; } ll ans=-1; for(int i=0; i<bt[u].size(); i++) { if(!ban[bt[u][i].se]) { ans=bt[u][i].fi; break; } } for(auto v:vt) ban[v]=0; return ans; } bool sub3() { for(int i=1; i<=n; i++) { dfs(i,0,i); } // for(int i=1; i<=n; i++) // { // for(auto [x,y]:bt[i]) cout<<x<<','<<y<<' '; // cout<<'\n'; // } for(int i=1; i<=q; i++) { ll t,y; cin>>t>>y; if(y>=200) { cout<<tr(t,y)<<'\n'; } else cout<<tr2(t,y)<<'\n'; } return 0; } int main() { online(); cin>>n>>m>>q; for(int i=1; i<=m; i++) { ll u,v; cin>>u>>v; if(u>v) swap(u,v); gr[u].push_back(v); } // if(q==1) return sub2(); return sub3(); }

Compilation message (stderr)

bitaro.cpp: In function 'void dfs(int, int, int)':
bitaro.cpp:106:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i=0; i<bt[u].size(); i++)
      |                  ~^~~~~~~~~~~~~
bitaro.cpp: In function 'int tr2(int, int)':
bitaro.cpp:156:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     for(int i=0; i<bt[u].size(); i++)
      |                  ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...