Submission #5052

# Submission time Handle Problem Language Result Execution time Memory
5052 2014-01-30T10:36:49 Z ainta Shymbulak (IZhO14_shymbulak) C++
69.33 / 100
140 ms 22504 KB
#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++)if (deg[i] == 1)Q[++t] = i;
	while (h < t){
		x = Q[++h];
		if (D[x][0].cnt == 0)D[x][0].cnt = 1;
		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 == 0)D[i][0].cnt = 1;
		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);
}
# Verdict Execution time Memory 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
# Verdict Execution time Memory Grader output
1 Correct 0 ms 15272 KB Output is correct
2 Correct 4 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 4 ms 15404 KB Output isn't correct
8 Correct 4 ms 15404 KB Output is correct
9 Correct 4 ms 15404 KB Output is correct
10 Incorrect 0 ms 15404 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 18176 KB Output isn't correct
2 Correct 60 ms 18572 KB Output is correct
3 Correct 52 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 140 ms 20816 KB Output isn't correct
7 Correct 96 ms 19892 KB Output is correct
8 Correct 92 ms 21608 KB Output is correct
9 Incorrect 92 ms 21608 KB Output isn't correct
10 Correct 80 ms 21872 KB Output is correct
11 Correct 92 ms 22108 KB Output is correct
12 Correct 96 ms 22504 KB Output is correct