Submission #13158

#	Time	Username	Problem	Language	Result	Execution time	Memory
13158		woqja125	Shymbulak (IZhO14_shymbulak)	C++14	32.67 / 100	114 ms	18200 KiB

shymbulak

#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 / 30
• Subtask 2: 6 / 20
• Subtask 3: 16.667 / 50