oj.uz

Submission #5060

# Submission time Handle Problem Language Result Execution time Memory
5060 2014-01-30T11:51:49 Z ainta Shymbulak (IZhO14_shymbulak) C++
59 / 100
 140 ms 21724 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_ * 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.0 / 30.0

# Verdict Execution time Memory 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
10.0 / 20.0

# Verdict Execution time Memory 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 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 0 ms 14624 KB Output isn't correct
8 Incorrect 0 ms 14624 KB Output isn't correct
9 Correct 4 ms 14624 KB Output is correct
10 Incorrect 0 ms 14624 KB Output isn't correct

Subtask #3
25.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 17396 KB Output isn't correct
2 Incorrect 60 ms 17792 KB Output isn't correct
3 Correct 48 ms 17528 KB Output is correct
4 Correct 44 ms 17660 KB Output is correct
5 Incorrect 44 ms 17660 KB Output isn't correct
6 Incorrect 140 ms 20036 KB Output isn't correct
7 Incorrect 100 ms 19112 KB Output isn't correct
8 Correct 92 ms 20828 KB Output is correct
9 Incorrect 104 ms 20828 KB Output isn't correct
10 Correct 88 ms 21092 KB Output is correct
11 Correct 112 ms 21328 KB Output is correct
12 Correct 112 ms 21724 KB Output is correct