제출 #68542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68542		hamzqq9	관광지 (IZhO14_shymbulak)	C++14	100 / 100	237 ms	59588 KiB

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);

}

컴파일 시 표준 에러 (stderr) 메시지

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 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50