답안 #5055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5055	2014-01-30T11:17:44 Z	ainta	관광지 (IZhO14_shymbulak)	C++	69.33 / 100	144 ms	21724 KB

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;
				}
			}
		}
	}
	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, cc, h = 1, t = 0, tp, k, C;
	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++;
		tp= Gap(Deq[h], i);
		if (cc >= m && tp == Len){
			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++;
			res += (long long)C * D2[i].cnt;
		}
		while (h <= t && D2[Deq[t]].a + dist(Deq[t], i) < D2[i].a) t--;
		Deq[++t] = i;
	}
}
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);
	return 0;
}

Subtask #1

24.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	14492 KB	Output is correct
2	Correct	0 ms	14492 KB	Output is correct
3	Correct	0 ms	14492 KB	Output is correct
4	Correct	0 ms	14492 KB	Output is correct
5	Incorrect	0 ms	14492 KB	Output isn't correct
6	Correct	0 ms	14492 KB	Output is correct
7	Correct	0 ms	14492 KB	Output is correct
8	Correct	0 ms	14492 KB	Output is correct
9	Correct	0 ms	14492 KB	Output is correct
10	Incorrect	0 ms	14492 KB	Output isn't correct
11	Correct	0 ms	14492 KB	Output is correct
12	Correct	0 ms	14492 KB	Output is correct
13	Incorrect	0 ms	14492 KB	Output isn't correct
14	Correct	0 ms	14492 KB	Output is correct
15	Correct	0 ms	14492 KB	Output is correct

Subtask #2

12.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	14492 KB	Output is correct
2	Correct	0 ms	14492 KB	Output is correct
3	Correct	4 ms	14492 KB	Output is correct
4	Incorrect	0 ms	14492 KB	Output isn't correct
5	Incorrect	0 ms	14624 KB	Output isn't correct
6	Correct	0 ms	14624 KB	Output is correct
7	Incorrect	4 ms	14624 KB	Output isn't correct
8	Correct	4 ms	14624 KB	Output is correct
9	Correct	4 ms	14624 KB	Output is correct
10	Incorrect	0 ms	14624 KB	Output isn't correct

Subtask #3

33.333 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	68 ms	17396 KB	Output isn't correct
2	Correct	68 ms	17792 KB	Output is correct
3	Correct	40 ms	17528 KB	Output is correct
4	Correct	48 ms	17660 KB	Output is correct
5	Incorrect	44 ms	17660 KB	Output isn't correct
6	Incorrect	144 ms	20036 KB	Output isn't correct
7	Correct	96 ms	19112 KB	Output is correct
8	Correct	100 ms	20828 KB	Output is correct
9	Incorrect	92 ms	20828 KB	Output isn't correct
10	Correct	84 ms	21092 KB	Output is correct
11	Correct	116 ms	21328 KB	Output is correct
12	Correct	100 ms	21724 KB	Output is correct