oj.uz

Submission #68542

# Submission time Handle Problem Language Result Execution time Memory
68542 2018-08-17T09:26:54 Z hamzqq9 Shymbulak (IZhO14_shymbulak) C++14
100 / 100
 237 ms 59588 KB 
#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],dp[N];
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;

} 

ii dfs3(int node,int ata) {

	ii mx={0,1};

	for(int i:v[node]) {

		if(i==ata || incyc[i]) continue ;

		ii deepest=dfs3(i,node);

		eval(mx,deepest,2);

		if(deepest.st>mx.st) {

			swap(deepest,mx);

		}
		else if(deepest.st==mx.st) {

			mx.nd+=deepest.nd;

		}

	}

	return {mx.st+1,mx.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]);

		}

		for(int node:nodes[i]) {

			if(incyc[node]) {

				dfs3(node,0);

			}

		}

		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:325:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
shymbulak.cpp:329:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 28536 KB Output is correct
2 Correct 36 ms 28772 KB Output is correct
3 Correct 33 ms 28852 KB Output is correct
4 Correct 35 ms 28852 KB Output is correct
5 Correct 27 ms 28852 KB Output is correct
6 Correct 26 ms 28852 KB Output is correct
7 Correct 26 ms 28852 KB Output is correct
8 Correct 27 ms 28852 KB Output is correct
9 Correct 28 ms 28852 KB Output is correct
10 Correct 27 ms 28956 KB Output is correct
11 Correct 29 ms 28956 KB Output is correct
12 Correct 28 ms 28956 KB Output is correct
13 Correct 27 ms 28956 KB Output is correct
14 Correct 28 ms 28956 KB Output is correct
15 Correct 29 ms 28956 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 28956 KB Output is correct
2 Correct 27 ms 28956 KB Output is correct
3 Correct 29 ms 28956 KB Output is correct
4 Correct 29 ms 28956 KB Output is correct
5 Correct 30 ms 29280 KB Output is correct
6 Correct 32 ms 29280 KB Output is correct
7 Correct 33 ms 29280 KB Output is correct
8 Correct 32 ms 29380 KB Output is correct
9 Correct 32 ms 29476 KB Output is correct
10 Correct 30 ms 29524 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 33468 KB Output is correct
2 Correct 111 ms 35040 KB Output is correct
3 Correct 121 ms 43644 KB Output is correct
4 Correct 90 ms 43644 KB Output is correct
5 Correct 82 ms 43644 KB Output is correct
6 Correct 237 ms 44092 KB Output is correct
7 Correct 160 ms 44396 KB Output is correct
8 Correct 143 ms 49836 KB Output is correct
9 Correct 144 ms 52096 KB Output is correct
10 Correct 195 ms 56128 KB Output is correct
11 Correct 175 ms 56720 KB Output is correct
12 Correct 231 ms 59588 KB Output is correct