oj.uz

Submission #5061

# Submission time Handle Problem Language Result Execution time Memory
5061 2014-01-30T12:31:32 Z ainta Shymbulak (IZhO14_shymbulak) C++
83.67 / 100
 156 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 (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

# 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 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

# 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 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

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