oj.uz

답안 #5059

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5059 2014-01-30T11:47:22 Z ainta 관광지 (IZhO14_shymbulak) C++
59 / 100
 148 ms 22504 KB 
#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_];
int deg[N_], Q[N_];
long long res;
struct Table{
	int a, cnt;
}D[N_][2], Deq2[N_], 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[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.0 / 30.0

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

Subtask #2
10.0 / 20.0

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

Subtask #3
25.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 18176 KB Output isn't correct
2 Incorrect 64 ms 18572 KB Output isn't correct
3 Correct 44 ms 18308 KB Output is correct
4 Correct 48 ms 18440 KB Output is correct
5 Incorrect 44 ms 18440 KB Output isn't correct
6 Incorrect 148 ms 20816 KB Output isn't correct
7 Incorrect 96 ms 19892 KB Output isn't correct
8 Correct 96 ms 21608 KB Output is correct
9 Incorrect 100 ms 21608 KB Output isn't correct
10 Correct 80 ms 21872 KB Output is correct
11 Correct 100 ms 22108 KB Output is correct
12 Correct 112 ms 22504 KB Output is correct