Submission #5056

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
5056	2014-01-30T11:29:58 Z	ainta	Shymbulak (IZhO14_shymbulak)	C++	65.17 / 100	1500 ms	22504 KB

shymbulak

#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;
				}
			}
		}
	}
	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 j;
	for (i = 0; i < m; i++){
		for (j = 0; j < m; j++){
			if (i != j && dist(i, j) * 2 <= m && Gap(i, j) == Len){
				res += (long long)D2[i].cnt * D2[j].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	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

12.0 / 20.0

#	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	4 ms	15272 KB	Output is correct
4	Incorrect	0 ms	15272 KB	Output isn't correct
5	Incorrect	0 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

Subtask #3

29.167 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	56 ms	18176 KB	Output isn't correct
2	Correct	68 ms	18572 KB	Output is correct
3	Execution timed out	1500 ms	18304 KB	Program timed out
4	Correct	32 ms	18440 KB	Output is correct
5	Incorrect	44 ms	18440 KB	Output isn't correct
6	Incorrect	156 ms	20816 KB	Output isn't correct
7	Correct	116 ms	19892 KB	Output is correct
8	Correct	100 ms	21608 KB	Output is correct
9	Incorrect	96 ms	21608 KB	Output isn't correct
10	Correct	144 ms	21872 KB	Output is correct
11	Correct	92 ms	22108 KB	Output is correct
12	Correct	104 ms	22504 KB	Output is correct