Submission #128744

#TimeUsernameProblemLanguageResultExecution timeMemory
128744faustaadpShymbulak (IZhO14_shymbulak)C++17
50 / 100
1562 ms17396 KiB
#include<bits/stdc++.h> typedef long long ll; #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; ll n,i,ta,tb,p[201010],b[201010],CS,ma,jum,has,j,K; vector<ll> v[201010],cyc,isi[201010],tom; pair<ll,ll> A[201010]; ll ST[2][1601601]; ll byk[2][1601601]; void dfs(ll aa) { b[aa]=1; ll ii; for(ii=0;ii<v[aa].size();ii++) { if(v[aa][ii]==p[aa]||b[v[aa][ii]]==2)continue; if(b[v[aa][ii]]) { ll tem=aa; cyc.pb(tem); while(tem!=v[aa][ii]) { tem=p[tem]; cyc.pb(tem); } } else { p[v[aa][ii]]=aa; dfs(v[aa][ii]); } } b[aa]=2; } void dfs1(ll aa,ll bb,ll cc) { isi[i].pb(aa); if(ma<cc) { ma=max(ma,cc); jum=0; } if(ma==cc) jum++; ll ii; for(ii=0;ii<v[aa].size();ii++) { if(b[v[aa][ii]])continue; if(v[aa][ii]==bb)continue; dfs1(v[aa][ii],aa,cc+1); } } void dfs2(ll aa,ll bb,ll cc) { //cout<<isi[i][j]<<" "<<aa<<" "<<cc<<"_\n"; if(ma<cc) { ma=max(ma,cc); jum=0; } if(ma==cc) jum++; ll ii; for(ii=0;ii<v[aa].size();ii++) { if(b[v[aa][ii]])continue; if(v[aa][ii]==bb)continue; dfs2(v[aa][ii],aa,cc+1); } } void upd(ll aa,ll bb,ll cc,ll dd,ll ee,ll ff,ll gg) { if(aa==bb) { ST[ff][ee]=dd; byk[ff][ee]=gg; } else { ll ce=(aa+bb)/2; if(cc<=ce) upd(aa,ce,cc,dd,ee*2,ff,gg); else upd(ce+1,bb,cc,dd,ee*2+1,ff,gg); ST[ff][ee]=max(ST[ff][ee*2],ST[ff][ee*2+1]); byk[ff][ee]=0; if(ST[ff][ee]==ST[ff][ee*2])byk[ff][ee]+=byk[ff][ee*2]; if(ST[ff][ee]==ST[ff][ee*2+1])byk[ff][ee]+=byk[ff][ee*2+1]; } //cout<<ff<<" "<<aa<<" "<<bb<<" "<<ee<<" "<<ST[ff][ee]<<" "<<byk[ff][ee]<<"\n"; } void cari(ll aa,ll bb,ll cc,ll dd,ll ee) { if(bb<cc||dd<aa)return ; else if(cc<=aa&&bb<=dd) tom.pb(ee); else { ll ce=(aa+bb)/2; cari(aa,ce,cc,dd,ee*2); cari(ce+1,bb,cc,dd,ee*2+1); } } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; for(i=1;i<=n;i++) { cin>>ta>>tb; v[ta].pb(tb); v[tb].pb(ta); } dfs(1); CS=cyc.size(); memset(b,0,sizeof(b)); for(i=0;i<CS;i++)b[cyc[i]]=1; for(i=0;i<CS;i++) { ma=-1; jum=0; dfs1(cyc[i],cyc[i],0); A[i]=mp(ma,jum); //cout<<cyc[i]<<" "<<A[i].fi<<" "<<A[i].se<<"\n"; } ma=-1; jum=0; for(i=0;i<CS;i++) { b[cyc[i]]=0; for(j=0;j<isi[i].size();j++) { //cout<<isi[i][j]<<"\n"; dfs2(isi[i][j],isi[i][j],0); } b[cyc[i]]=1; } //jum=0; K=CS*2-1; for(i=0;i<CS*2;i++) { upd(0,K,i,i+A[i%CS].fi,1,0,A[i%CS].se); upd(0,K,i,(K-i)+A[i%CS].fi,1,1,A[i%CS].se); } for(i=0;i<CS;i++) { ll L,R,C; L=i+1;R=i+(CS)/2;C=A[i].fi; while(L>=CS) { L-=CS; R-=CS; } C-=(L-1); tom.clear();cari(0,K,L,R,1); // cout<<cyc[i]<<" "<<L<<" "<<R<<" "<<C<<"\n"; for(j=0;j<tom.size();j++) { // cout<<cyc[i]<<" "<<ST[0][tom[j]]+C<<"@\n"; if(ma<(ST[0][tom[j]]+C)) { ma=(ST[0][tom[j]]+C); jum=0; } if(ma==(ST[0][tom[j]]+C)) { jum+=A[i].se*byk[0][tom[j]]; // cout<<cyc[i]<<" "<<ma<<" "<<jum<<"_\n"; } } L=(i-(CS)/2);R=i-1;C=A[i].fi; while(L<0) { L+=CS; R+=CS; } C+=(R+1)-K; // cout<<cyc[i]<<" "<<L<<" "<<R<<" "<<C<<"__\n"; tom.clear();cari(0,K,L,R,1); for(j=0;j<tom.size();j++) { // cout<<ST[1][tom[j]]+C<<"@\n"; if(ma<(ST[1][tom[j]]+C)) { ma=(ST[1][tom[j]]+C); jum=0; } if(ma==(ST[1][tom[j]]+C)) { jum+=A[i].se*byk[1][tom[j]]; // cout<<cyc[i]<<" "<<ma<<" "<<jum<<"\n"; } } } // for(i=0;i<CS;i++) // { // ll tam=1; // for(j=i+1;j<=(i+(CS)/2);j++) // { // if(ma<(tam+A[i].fi+A[j%CS].fi)) // { // ma=(tam+A[i].fi+A[j%CS].fi); // jum=0; // } // if(ma==(tam+A[i].fi+A[j%CS].fi)) // { // // cout<<cyc[i]<<" "<<cyc[j%CS]<<" "<<(tam+A[i].fi+A[j%CS].fi)<<"\n"; // jum+=A[i].se*A[j%CS].se; // } // tam++; // } // tam=1; // for(j=i-1;j>=(i-(CS)/2);j--) // { // if(ma<(tam+A[i].fi+A[(j+CS)%CS].fi)) // { // ma=(tam+A[i].fi+A[(j+CS)%CS].fi); // jum=0; // } // if(ma==(tam+A[i].fi+A[(j+CS)%CS].fi)) // { // // cout<<cyc[i]<<" "<<cyc[(j+CS)%CS]<<" "<<ma<<"\n"; // jum+=A[i].se*A[(j+CS)%CS].se; // } // tam++; // } // } //cout<<ma<<" "<<jum<<"\n"; jum/=2; cout<<jum<<"\n"; }

Compilation message (stderr)

shymbulak.cpp: In function 'void dfs(ll)':
shymbulak.cpp:17:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs1(ll, ll, ll)':
shymbulak.cpp:49:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs2(ll, ll, ll)':
shymbulak.cpp:67:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:135:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<isi[i].size();j++)
           ~^~~~~~~~~~~~~~
shymbulak.cpp:161:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<tom.size();j++)
           ~^~~~~~~~~~~
shymbulak.cpp:184:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<tom.size();j++)
           ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...