제출 #5060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5060		ainta	관광지 (IZhO14_shymbulak)	C++98	59 / 100	140 ms	21724 KiB

shymbulak

#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
#define N_ 200010
vector<int>E[N_];
int n, Len, Cyc[N_], m, Deq[N_ * 2];
int deg[N_], Q[N_];
long long res;
struct Table{
	int a, cnt;
}D[N_][2], D2[N_];
void Find_Cycle(int st)
{
	int x = st, i, p = -1;
	while (1){
		Cyc[m++] = x;
		for (i = 0; i < E[x].size(); i++){
			if (deg[E[x][i]] != 1 && p != E[x][i])break;
		}
		p = x;
		x = E[x][i];
		if (x == st)break;
	}
	for (i = 0; i < m; i++)D2[i] = D[Cyc[i]][0];
}
void PrePro(){
	int i, h = 0, t = 0, x, y, ck, tp;
	for (i = 1; i <= n; i++){
		D[i][0].cnt = 1;
		if (deg[i] == 1)Q[++t] = i;
	}
	while (h < t){
		x = Q[++h];
		for (i = 0; i < E[x].size(); i++){
			y = E[x][i];
			if (deg[y] != 1){
				deg[y]--;
				if (deg[y] == 1)Q[++t] = y;
				tp = D[x][0].a + 1;
				if (D[y][0].a <= tp){
					if (D[y][0].a < tp)D[y][1] = D[y][0], D[y][0].cnt = 0;
					D[y][0].a = tp, D[y][0].cnt += D[x][0].cnt;
				}
				else if (D[y][1].a <= tp){
					if (D[y][1].a < tp)D[y][1].cnt = 0;
					D[y][1].a = tp, D[y][1].cnt += D[x][0].cnt;
				}
				tp = D[x][1].a + 1;
				if (D[x][1].cnt && D[y][1].a <= tp){
					if (D[y][1].a < tp)D[y][1].cnt = 0;
					D[y][1].a = tp, D[y][1].cnt += D[x][1].cnt;
				}
			}
		}
	}
	ck = 1;
	for (i = 1; i <= n; i++){
		if (D[i][0].cnt >= 2){
			if (Len < D[i][0].a * 2)Len = D[i][0].a * 2;
		}
		else if (Len < D[i][0].a + D[i][1].a)Len = D[i][0].a + D[i][1].a;
	}
	for (i = 1; i <= n; i++)if (deg[i] != 1)break;
	Find_Cycle(i);
}
int dist(int a, int b){
	return a>b ? m + b - a : b - a;
}
int Gap(int a, int b){
	return dist(a, b) + D2[a].a + D2[b].a;
}
void Pro1(){
	int i, cc, h = 1, t = 0;
	Deq[++t] = 0;
	for (i = 1, cc = 1; cc < 2 * m; cc++, i++){
		if (i == m)i = 0;
		while (h <= t && dist(Deq[h], i) * 2 > m)h++;
		Len = max(Len, Gap(Deq[h], i));
		while (h <= t && D2[Deq[t]].a + dist(Deq[t], i) <= D2[i].a) t--;
		Deq[++t] = i;
	}
}
void TreeMax(){
	int i;
	long long tp;
	for (i = 1; i <= n; i++){
		if (D[i][0].cnt >= 2){
			if (Len == D[i][0].a * 2){
				tp = D[i][0].cnt;
				res += tp * (tp - 1) / 2LL;
			}
		}
		else if (D[i][0].a + D[i][1].a == Len){
			res += (long long)D[i][0].cnt * D[i][1].cnt;
		}
	}
}
void Pro2()
{
	int i, C = 0, cc, h = 1, t = 0, tp, k;
	Deq[++t] = 0, C += D2[0].cnt;
	for (i = 1, cc = 1; cc < 2 * m; cc++, i++){
		if (i == m)i = 0;
		while (h <= t && dist(Deq[h], i) * 2 > m) C -= D2[Deq[h]].cnt, h++;
		if (C == 0){
			C = D2[Deq[h]].cnt;
			k = h + 1;
			while (k <= t && Gap(Deq[h], i) == Gap(Deq[k], i))C += D2[Deq[k]].cnt, k++;
		}
		tp = Gap(Deq[h], i);
		if (cc >= m && tp == Len){
			res += (long long)C * D2[i].cnt;
		}
		while (h <= t && D2[Deq[t]].a + dist(Deq[t], i) < D2[i].a) t--;
		if (h > t) C = 0;
		Deq[++t] = i;
		if (D2[Deq[h]].a + dist(Deq[h], i) == D2[i].a) C += D2[i].cnt;
	}
}
int main(){
	int i, a, b;
	scanf("%d", &n);
	for (i = 0; i < n; i++){
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);
		deg[a]++, deg[b]++;
	}
	PrePro();
	Pro1();
	TreeMax();
	Pro2();
	printf("%lld\n", res);
}

• Subtask 1: 24 / 30
• Subtask 2: 10 / 20
• Subtask 3: 25 / 50