답안 #5061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5061	2014-01-30T12:31:32 Z	ainta	관광지 (IZhO14_shymbulak)	C++	83.67 / 100	156 ms	23480 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_];
bool v[N_];
long long res, S[N_];
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;
						v[y] = false, S[y] = (long long)D[y][1].cnt*D[x][0].cnt;
					}
					else if (v[y] == false)v[y] = true, S[y] = 0;
					S[y] += (long long)D[y][0].cnt * D[x][0].cnt;
					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;
						if (!v[y])S[y] = 0;
					}
					if (!v[y]) S[y] += (long long)D[y][0].cnt*D[x][0].cnt;
					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 (v[i]){
			if (Len == D[i][0].a * 2)res += S[i];
		}
		else if (Len == D[i][0].a + D[i][1].a) res += S[i];
	}
}
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.0 / 30.0

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

Subtask #2

18.0 / 20.0

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

Subtask #3

41.667 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	60 ms	19152 KB	Output isn't correct
2	Correct	68 ms	19548 KB	Output is correct
3	Correct	52 ms	19284 KB	Output is correct
4	Correct	36 ms	19416 KB	Output is correct
5	Correct	52 ms	19416 KB	Output is correct
6	Incorrect	156 ms	21792 KB	Output isn't correct
7	Correct	100 ms	20868 KB	Output is correct
8	Correct	100 ms	22584 KB	Output is correct
9	Correct	84 ms	22584 KB	Output is correct
10	Correct	84 ms	22848 KB	Output is correct
11	Correct	104 ms	23084 KB	Output is correct
12	Correct	100 ms	23480 KB	Output is correct