oj.uz

Submission #13186

# Submission time Handle Problem Language Result Execution time Memory
13186 2015-02-01T13:42:49 Z woqja125 Shymbulak (IZhO14_shymbulak) C++14
83.67 / 100
 109 ms 30508 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;
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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 22484 KB Output is correct
2 Incorrect 0 ms 22484 KB Output isn't correct
3 Correct 3 ms 22484 KB Output is correct
4 Correct 0 ms 22484 KB Output is correct
5 Correct 0 ms 22484 KB Output is correct
6 Correct 0 ms 22484 KB Output is correct
7 Correct 0 ms 22484 KB Output is correct
8 Correct 0 ms 22484 KB Output is correct
9 Correct 0 ms 22484 KB Output is correct
10 Correct 0 ms 22484 KB Output is correct
11 Correct 0 ms 22484 KB Output is correct
12 Correct 4 ms 22484 KB Output is correct
13 Incorrect 0 ms 22484 KB Output isn't correct
14 Correct 0 ms 22484 KB Output is correct
15 Correct 0 ms 22484 KB Output is correct

Subtask #2
16.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22484 KB Output is correct
2 Incorrect 0 ms 22484 KB Output isn't correct
3 Correct 1 ms 22484 KB Output is correct
4 Correct 0 ms 22484 KB Output is correct
5 Correct 5 ms 22616 KB Output is correct
6 Incorrect 0 ms 22616 KB Output isn't correct
7 Correct 5 ms 22616 KB Output is correct
8 Correct 5 ms 22616 KB Output is correct
9 Correct 5 ms 22616 KB Output is correct
10 Correct 3 ms 22616 KB Output is correct

Subtask #3
41.667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 25648 KB Output is correct
2 Correct 58 ms 26048 KB Output is correct
3 Correct 50 ms 25652 KB Output is correct
4 Correct 21 ms 25780 KB Output is correct
5 Correct 42 ms 25912 KB Output is correct
6 Correct 109 ms 28420 KB Output is correct
7 Correct 84 ms 27496 KB Output is correct
8 Correct 84 ms 29212 KB Output is correct
9 Correct 92 ms 29212 KB Output is correct
10 Correct 88 ms 29612 KB Output is correct
11 Incorrect 102 ms 30112 KB Output isn't correct
12 Incorrect 107 ms 30508 KB Output isn't correct