Submission #392637

#TimeUsernameProblemLanguageResultExecution timeMemory
392637vanicShymbulak (IZhO14_shymbulak)C++14
70 / 100
269 ms16468 KiB
#include <iostream> #include <cmath> #include <algorithm> #include <cstdio> #include <set> #include <stack> #include <map> #include <vector> #include <queue> #include <cstring> #include <array> #include <bitset> using namespace std; typedef long long ll; const int maxn=2e5+5, Log=18, pot=(1<<Log); struct tournament{ int t[pot*2]; int k[pot*2]; int prop[pot*2]; void propagate(int x){ if(!prop[x]){ return; } t[x]+=prop[x]; if(x<pot){ prop[x*2]+=prop[x]; prop[x*2+1]+=prop[x]; } prop[x]=0; } void cisti(int L, int D, int x, int val){ propagate(x); if(L==val && D==val){ return; } if((L+D)/2>=val){ cisti(L, (L+D)/2, x*2, val); } else{ cisti((L+D)/2+1, D, x*2+1, val); } } void update1(int x, int val, int komb){ cisti(0, pot-1, 1, x-pot); t[x]=val; k[x]=komb; for(x/=2; x>0; x/=2){ propagate(x*2); propagate(x*2+1); if(t[x*2]>t[x*2+1]){ t[x]=t[x*2]; k[x]=k[x*2]; } else if(t[x*2]<t[x*2+1]){ t[x]=t[x*2+1]; k[x]=k[x*2+1]; } else{ t[x]=t[x*2]; k[x]=k[x*2]+k[x*2+1]; } } } void update(int x, int val){ t[x]+=val; for(x/=2; x>0; x/=2){ propagate(x*2); propagate(x*2+1); if(t[x*2]>t[x*2+1]){ t[x]=t[x*2]; k[x]=k[x*2]; } else if(t[x*2]<t[x*2+1]){ t[x]=t[x*2+1]; k[x]=k[x*2+1]; } else{ t[x]=t[x*2]; k[x]=k[x*2]+k[x*2+1]; } } } void update2(int L, int D, int x, int l, int d, int val){ propagate(x); if(L>=l && D<=d){ update(x, val); if(x<pot){ prop[x*2]+=val; prop[x*2+1]+=val; } return; } if((L+D)/2>=l){ update2(L, (L+D)/2, x*2, l, d, val); } if((L+D)/2+1<=d){ update2((L+D)/2+1, D, x*2+1, l, d, val); } } }; vector < int > ms[maxn]; bitset < maxn > bio; vector < int > sad; vector < int > da; bitset < maxn > cik; tournament T; bool ciklus(int x, int prosl){ if(bio[x]){ bool p=0; for(int i=0; i<(int)sad.size(); i++){ if(sad[i]==x){ p=1; } if(p){ da.push_back(sad[i]); cik[sad[i]]=1; } } return 1; } sad.push_back(x); bio[x]=1; for(int i=0; i<(int)ms[x].size(); i++){ if(ms[x][i]!=prosl){ if(ciklus(ms[x][i], x)){ return 1; } } } bio[x]=0; sad.pop_back(); return 0; } vector < int > dulj; void siri(int x, int dep){ // cout << "proso " << x << endl; bio[x]=1; dulj.push_back(dep); for(int i=0; i<(int)ms[x].size(); i++){ if(!cik[ms[x][i]] && !bio[ms[x][i]]){ siri(ms[x][i], dep+1); } } } vector < array < int, 4 > > svi; ll komba; int curr; int bfs(int x, int prosl){ queue < pair < int, int > > q; q.push({x, prosl}); pair < int, int > p; while(!q.empty()){ p=q.front(); q.pop(); prosl=p.second; x=p.first; for(int i=0; i<(int)ms[x].size(); i++){ if(ms[x][i]!=prosl && !cik[ms[x][i]]){ // cout << "pusham " << ms[x][i] << endl; q.push({ms[x][i], x}); } } } return x; } vector < int > put; bool dfs(int x, int prosl, int y){ put.push_back(x); if(x==y){ return 1; } for(int i=0; i<(int)ms[x].size(); i++){ if(ms[x][i]!=prosl && !cik[ms[x][i]]){ if(dfs(ms[x][i], x, y)){ return 1; } } } put.pop_back(); return 0; } int nadji(int x, int prosl, int d){ if(!d){ return 1; } d--; int br=0; for(int i=0; i<(int)ms[x].size(); i++){ if(ms[x][i]!=prosl && !cik[ms[x][i]]){ br+=nadji(ms[x][i], x, d); } } return br; } void rijesi(int x){ int poc=x; cik[poc]=0; x=bfs(x, x); int y=bfs(x, x); dfs(x, x, y); int dulj=put.size(); /* for(int i=0; i<dulj; i++){ cout << put[i] << ' '; } cout << endl;*/ curr=dulj-1; int br1, br2; if(dulj&1){ br1=nadji(put[dulj/2], put[dulj/2], dulj/2); komba=(ll)br1*(br1-1)/2; } else{ br1=nadji(put[dulj/2-1], put[dulj/2], dulj/2-1); br2=nadji(put[dulj/2], put[dulj/2-1], dulj/2-1); komba=(ll)br1*br2; } cik[poc]=1; put.clear(); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; int a, b; for(int i=0; i<n; i++){ cin >> a >> b; a--; b--; ms[a].push_back(b); ms[b].push_back(a); } ciklus(0, 0); bio.reset(); /* for(int i=0; i<n; i++){ if(cik[i]){ cout << i << ' '; } } cout << endl;*/ int br1; int val1; int pos; int m=da.size(); for(int i=0; i<m; i++){ // cout << da[i] << ' '; siri(da[i], 0); sort(dulj.begin(), dulj.end()); br1=0; pos=dulj.size()-1; val1=dulj.back(); while(pos>-1 && val1==dulj[pos]){ br1++; pos--; } svi.push_back({val1, br1}); dulj.clear(); } // cout << endl; /* for(int i=0; i<m; i++){ cout << svi[i][0] << ' ' << svi[i][1] << endl; }*/ int l1, d1, l2, d2; for(int i=0; i<m; i++){ T.update1(i+pot, svi[i][0], svi[i][1]); } int maksi=0; ll komb=0; int val; for(int i=0; i<m; i++){ T.update1(i+pot, -maxn, 0); if(!i){ if(!(m&1) && i<m/2){ T.update1(i+pot+m/2, svi[i+m/2][0], svi[i+m/2][1]*2); } for(int j=1; j<m; j++){ T.update2(0, pot-1, 1, j, j, min(j, m-j)); } } else{ if(!(m&1) && i<m/2){ T.update1(i+pot+m/2, svi[i+m/2][0]+m/2-1, svi[i+m/2][1]*2); } l1=i-m/2; d1=i-1; if(l1<0){ l2=l1+m; d2=m-1; l1=0; T.update2(0, pot-1, 1, l2, d2, 1); } T.update2(0, pot-1, 1, l1, d1, 1); l1=i; d1=i+m/2-1; if(d1>=m){ l2=0; d2=d1-m; d1=m-1; T.update2(0, pot-1, 1, l2, d2, -1); } T.update2(0, pot-1, 1, l1, d1, -1); } val=T.t[1]+svi[i][0]; // cout << val << ' ' << svi[i][1] << ' ' << T.k[1] << endl; if(val>maksi){ maksi=val; komb=T.k[1]*svi[i][1]; } else if(val==maksi){ komb+=T.k[1]*svi[i][1]; } if(!(m&1) && i<m/2){ T.update1(i+pot+m/2, svi[i+m/2][0]+m/2, svi[i+m/2][1]); } } bio.reset(); for(int i=0; i<m; i++){ rijesi(da[i]); if(curr>maksi){ maksi=curr; komb=komba; } else if(curr==maksi){ komb+=komba; } } cout << komb << '\n'; // cout << maksi << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...