제출 #13186

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13186		woqja125	관광지 (IZhO14_shymbulak)	C++14	83.67 / 100	109 ms	30508 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;
long long solve(int , long long);
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;
	}
	int max = 0;
	long long maxC = 0;
	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 > max)
		{
			max = dist[xx] + dist[x] + 1;
			maxC = 1ll * distC[xx] * distC[x];
		}
		else if(dist[xx] + dist[x] + 1 == max)
		{
			maxC += 1ll*distC[xx]*dist[x];
		}

		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);
	printf("%lld", solve(max, maxC));
	return 0;
}

int im[1050000];
long long imc[1050000];
int b;

inline int cn(int x){return dist[cycles[(x)%CC]];}
inline int cd(int x){return distC[cycles[(x)%CC]];}

void add(int &m, long long &mC, int m1, long long mc1, int m2, long long mc2)
{
	if(m1 == m2)
	{
		m = m1;
		mC = mc1 + mc2;
	}
	else if(m1 > m2)
	{
		m = m1;
		mC = mc1;
	}
	else
	{
		m = m2;
		mC = mc2;
	}
}

void get(int &rm, long long &rmc, int f, int r)
{
	f+=b; r+=b;
	rm = rmc = 0;
	while(f<r)
	{
		if(f%2 == 1) { add(rm, rmc, rm, rmc, im[f], imc[f]); f++; }
		if(r%2 == 0) { add(rm, rmc, rm, rmc, im[r], imc[r]); r--; }
		f/=2; r/=2;
	}
	if(f==r) add(rm, rmc, rm, rmc, im[f], imc[f]);
}

long long solve(int max, long long maxC)
{
	int i;
	for(b=1; b<=2*CC; b*=2);
	for(i=0; i<2*CC; i++)
	{
		im[b+i] = cn(i) + i;
		imc[b+i] = cd(i);
	}
	for(i=b-1; i>=1; i--) add(im[i], imc[i], im[i*2], imc[i*2], im[i*2+1], imc[i*2+1]);
	int tm;
	long long tmc;
	int j;
	for(j=0; j <= CC-j; j++);
	for(i=0; i<CC; i++)
	{
		get(tm, tmc, i+1, j-1);
		add(max, maxC, max, maxC, tm-i+cn(i), tmc*cd(i));
		j++;
	}
	return maxC;
}

• Subtask 1: 26 / 30
• Subtask 2: 16 / 20
• Subtask 3: 41.667 / 50