#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 100000000
#define MOD 1000000007
#define N 400005
#define MAX 10000006
#define LOG 30
#define KOK 200
using namespace std;
int n,x,y,gr;
bool flag;
int dep[N],tot_cyc[N],incyc[N],vis[N];
ii deep;
ii S[4][N*4];
ll cnt[N];
vector<int> went,nodes[N],v[N];
vector<ii> deeps[N];
void merge(ii& a,ii b,ii c) {
if(b.st==c.st) {
a.st=b.st;
a.nd=b.nd+c.nd;
return ;
}
if(b.st<c.st) swap(b,c);
a=b;
}
ii get(int node,int bas,int son,int x,int y,int ty) {
if(x>y) return {-inf,0};
if(bas>y || son<x) return {-inf,0};
if(bas>=x && son<=y) return S[ty][node];
ii L=get(node*2,bas,orta,x,y,ty);
ii R=get(node*2+1,orta+1,son,x,y,ty);
ii res;
merge(res,L,R);
return res;
}
void build(int node,int bas,int son,int gr) {
if(bas==son) {
S[0][node]={bas+deeps[gr][bas].st,deeps[gr][bas].nd};
S[1][node]={-bas+deeps[gr][bas].st,deeps[gr][bas].nd};
S[2][node]={bas+deeps[gr][bas].st,deeps[gr][bas].nd};
S[3][node]={-bas+deeps[gr][bas].st,deeps[gr][bas].nd};
return ;
}
build(node*2,bas,orta,gr);
build(node*2+1,orta+1,son,gr);
for(int i=0;i<4;i++) merge(S[i][node],S[i][node*2],S[i][node*2+1]);
}
void eval(ii x,ii y,int add) {
if(x.st+y.st<0) return ;
cnt[x.st+y.st]+=1ll*add*x.nd*y.nd;
}
void dfs2(int node,int ata) {
dep[node]=dep[ata]+1;
if(deep.st<dep[node]) {
deep.st=dep[node];
deep.nd=1;
}
else if(deep.st==dep[node]) {
deep.nd++;
}
for(int i:v[node]) {
if(incyc[i] || i==ata) continue ;
dfs2(i,node);
}
}
void cycle_found(int node) {
flag=true;
for(int i=sz(went)-1;i>=0;i--) {
incyc[went[i]]=1;
tot_cyc[gr]++;
if(went[i]==node) return ;
}
assert(0);
}
void dfs(int node,int ata) {
if(vis[node]) {
if(!flag) cycle_found(node);
return ;
}
went.pb(node);
vis[node]=1;
nodes[gr].pb(node);
for(int i:v[node]) {
if(i==ata) continue ;
dfs(i,node);
}
went.ppb();
}
void find_and_count_max() {
dep[0]=-1;
for(int i=1;i<=n;i++) {
if(!vis[i]) {
++gr;
flag=false;
dfs(i,0);
}
}
for(int i=1;i<=gr;i++) {
deeps[i].pb({-1,0});
for(int node:nodes[i]) {
if(incyc[node]) {
deep={-1,0};
dfs2(node,0);
deeps[i].pb(deep);
}
}
}
for(int i=1;i<=gr;i++) {
int btlptr=1;
int strptr=0;
build(1,1,tot_cyc[i],gr);
/*printf("ORDER IS\n");
for(int j=0;j<sz(nodes[i]);j++) if(incyc[nodes[i][j]]) printf("%d ",nodes[i][j]);
puts("");*/
for(int j=1;j<=tot_cyc[i];j++) {
while(btlptr<=tot_cyc[i] && j+tot_cyc[i]-btlptr>btlptr-j) btlptr++;
while(strptr+1<=tot_cyc[i] && tot_cyc[i]-j+(strptr+1)<j-(strptr+1)) strptr++;
// printf("current --> %d bigtoleft-->%d smalltoright-->%d\n",j,btlptr,strptr);
ii g1_max=get(1,1,tot_cyc[i],1,strptr,0);
g1_max.st+=tot_cyc[i]-j;
ii g2_max=get(1,1,tot_cyc[i],strptr+1,j-1,1);
g2_max.st+=j;
ii g3_max=get(1,1,tot_cyc[i],j+1,btlptr-1,2);
g3_max.st+=-j;
ii g4_max=get(1,1,tot_cyc[i],btlptr,tot_cyc[i],3);
g4_max.st+=j+tot_cyc[i];
eval(deeps[i][j],g1_max,1);
eval(deeps[i][j],g2_max,1);
eval(deeps[i][j],g3_max,1);
eval(deeps[i][j],g4_max,1);
/*printf("gmax1.st-->%d gmax1.nd-->%d\n",g1_max.st,g1_max.nd);
printf("gmax2.st-->%d gmax2.nd-->%d\n",g2_max.st,g2_max.nd);
printf("gmax3.st-->%d gmax3.nd-->%d\n",g3_max.st,g3_max.nd);
printf("gmax4.st-->%d gmax4.nd-->%d\n",g4_max.st,g4_max.nd);*/
//printf("cnt[4]-->%lld\n",cnt[4]);
}
if(tot_cyc[i]&1) continue ;
int mid=tot_cyc[i]/2+1;
#define form(x) (x>tot_cyc[i]?x-tot_cyc[i]:x)
for(int j=1;j<=tot_cyc[i];j++,mid++) {
mid=form(mid);
ii gg=deeps[i][mid];
//printf("%d %d\n",j,mid);
gg.st+=tot_cyc[i]/2;
eval(deeps[i][j],gg,1);
}
}
}
int main() {
// freopen("input.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d %d",&x,&y);
v[x].pb(y);
v[y].pb(x);
}
find_and_count_max();
for(int i=N-1;i>=1;i--) {
if(cnt[i]) {
printf("%lld\n",cnt[i]/2);
return 0;
}
}
assert(0);
}
Compilation message
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:286:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
shymbulak.cpp:290:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x,&y);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
28536 KB |
Output is correct |
| 2 |
Incorrect |
27 ms |
28536 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
28684 KB |
Output is correct |
| 2 |
Incorrect |
27 ms |
28712 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
110 ms |
32936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
