oj.uz

Submission #5062

# Submission time Handle Problem Language Result Execution time Memory
5062 2014-01-30T12:35:07 Z ainta Shymbulak (IZhO14_shymbulak) C++
100 / 100
 148 ms 23480 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_];
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 (v[i]){
			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
30.0 / 30.0

# Verdict Execution time Memory 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 Correct 0 ms 16248 KB Output is correct
11 Correct 0 ms 16248 KB Output is correct
12 Correct 0 ms 16248 KB Output is correct
13 Correct 0 ms 16248 KB Output is correct
14 Correct 0 ms 16248 KB Output is correct
15 Correct 0 ms 16248 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16248 KB Output is correct
2 Correct 4 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 0 ms 16380 KB Output is correct
6 Correct 0 ms 16380 KB Output is correct
7 Correct 0 ms 16380 KB Output is correct
8 Correct 0 ms 16380 KB Output is correct
9 Correct 0 ms 16380 KB Output is correct
10 Correct 4 ms 16380 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 19152 KB Output is correct
2 Correct 64 ms 19548 KB Output is correct
3 Correct 52 ms 19284 KB Output is correct
4 Correct 48 ms 19416 KB Output is correct
5 Correct 40 ms 19416 KB Output is correct
6 Correct 148 ms 21792 KB Output is correct
7 Correct 104 ms 20868 KB Output is correct
8 Correct 100 ms 22584 KB Output is correct
9 Correct 92 ms 22584 KB Output is correct
10 Correct 88 ms 22848 KB Output is correct
11 Correct 92 ms 23084 KB Output is correct
12 Correct 112 ms 23480 KB Output is correct