oj.uz

답안 #13158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13158 2015-02-01T09:35:33 Z woqja125 관광지 (IZhO14_shymbulak) C++14
32.67 / 100
 114 ms 18200 KB 
#include<stdio.h>
#include<vector>
#include<queue>
std::vector<int> map[200001];
int deg[200001];
int n;
int dist[200001], distC[200001];
int v[200001];
int cycles[200001], CC = 0;
inline int cn(int x){return dist[cycles[(x)%CC]];}
inline int cd(int x){return distC[cycles[(x)%CC]];}
int main()
{
	int i, x, xx;
	scanf("%d", &n);
	for(i=1; i<=n; i++)
	{
		scanf("%d%d", &x, &xx);
		map[x].push_back(xx);
		map[xx].push_back(x);
		deg[x]++;
		deg[xx]++;
	}
	std::queue<int> Q;
	for(i=1; i<=n; i++)
	{
		if(deg[i] == 1)Q.push(i);
		distC[i] = 1;
	}
	while(!Q.empty())
	{
		x = Q.front();
		Q.pop();
		v[x] = true;
		for(int t :map[x]) if(v[t] == false){ xx=t; break; }
		deg[xx]--;
		if(deg[xx] == 1) Q.push(xx);
		if(dist[xx] < dist[x]+1)
		{
			dist[xx] = dist[x]+1;
			distC[xx] = distC[x];
		}
		else if(dist[xx] == dist[x] + 1) distC[xx]+=distC[x];
	}
	for(i=1; i<=n; i++) if(deg[i] != 1) break;
	xx = x = i;
	do
	{
		v[xx] = true;
		cycles[CC++] = xx;
		int tx=-1;
		for(int t: map[xx]) if(!v[t]){ tx = t; break;}
		xx = tx;
	}while(xx!=-1);
	int max;
	long long C;
	max = C = 0;
	int Allmax;
	long long AllC;
	int j;
	for(j=1; j-i<=CC-j; j++)
	{
		if(cn(j)+j > max)
		{
			max = cn(j)+j;
			C = cd(j);
		}
		else if(cn(j)+j == max) C+=cd(j);
	}
	Allmax = max + cn(0);
	AllC = 1ll*C*cd(0);
	for(i=1; i<CC; i++)
	{
		max --;
		if(cn(j)+j-i > max)
		{
			max = cn(j)+j-i;
			C = cd(j);
		}
		else if(cn(j)+j-i == max) C+=cd(j);

		if(max + cn(i) > Allmax)
		{
			Allmax = max+cn(i);
			AllC = 1ll*cd(i)*C;
		}
		else if(max +cn(i) == Allmax)
		{
			AllC += 1ll*cd(i)*C;
		}

		j++;
	}
	printf("%lld", AllC);
	return 0;
}

Subtask #1
10.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 10176 KB Output is correct
2 Incorrect 0 ms 10176 KB Output isn't correct
3 Incorrect 0 ms 10176 KB Output isn't correct
4 Incorrect 0 ms 10176 KB Output isn't correct
5 Incorrect 0 ms 10176 KB Output isn't correct
6 Incorrect 0 ms 10176 KB Output isn't correct
7 Incorrect 0 ms 10176 KB Output isn't correct
8 Correct 0 ms 10176 KB Output is correct
9 Incorrect 0 ms 10176 KB Output isn't correct
10 Incorrect 0 ms 10176 KB Output isn't correct
11 Correct 0 ms 10176 KB Output is correct
12 Correct 2 ms 10176 KB Output is correct
13 Incorrect 0 ms 10176 KB Output isn't correct
14 Incorrect 0 ms 10176 KB Output isn't correct
15 Correct 2 ms 10176 KB Output is correct

Subtask #2
6.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 10176 KB Output is correct
2 Incorrect 0 ms 10176 KB Output isn't correct
3 Correct 0 ms 10176 KB Output is correct
4 Incorrect 3 ms 10176 KB Output isn't correct
5 Incorrect 0 ms 10308 KB Output isn't correct
6 Incorrect 3 ms 10308 KB Output isn't correct
7 Incorrect 2 ms 10308 KB Output isn't correct
8 Incorrect 2 ms 10308 KB Output isn't correct
9 Correct 2 ms 10308 KB Output is correct
10 Incorrect 2 ms 10308 KB Output isn't correct

Subtask #3
16.667 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 67 ms 13340 KB Output isn't correct
2 Incorrect 57 ms 13740 KB Output isn't correct
3 Correct 52 ms 13344 KB Output is correct
4 Correct 53 ms 13472 KB Output is correct
5 Incorrect 39 ms 13604 KB Output isn't correct
6 Incorrect 114 ms 16112 KB Output isn't correct
7 Incorrect 74 ms 15188 KB Output isn't correct
8 Correct 78 ms 16904 KB Output is correct
9 Incorrect 87 ms 16904 KB Output isn't correct
10 Correct 73 ms 17304 KB Output is correct
11 Incorrect 82 ms 17804 KB Output isn't correct
12 Incorrect 96 ms 18200 KB Output isn't correct