답안 #68542 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68542	2018-08-17T09:26:54 Z	hamzqq9	관광지 (IZhO14_shymbulak)	C++14	100 / 100	237 ms	59588 KB

shymbulak

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #68542

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 20.0 / 20.0

Subtask #3 50.0 / 50.0

Subtask #1
30.0 / 30.0

Subtask #2
20.0 / 20.0

Subtask #3
50.0 / 50.0