oj.uz

Submission #13188

# Submission time Handle Problem Language Result Execution time Memory
13188 2015-02-01T13:55:57 Z woqja125 Shymbulak (IZhO14_shymbulak) C++14
100 / 100
 126 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]*distC[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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 22484 KB Output is correct
2 Correct 3 ms 22484 KB Output is correct
3 Correct 0 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 3 ms 22484 KB Output is correct
11 Correct 3 ms 22484 KB Output is correct
12 Correct 0 ms 22484 KB Output is correct
13 Correct 0 ms 22484 KB Output is correct
14 Correct 0 ms 22484 KB Output is correct
15 Correct 0 ms 22484 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 25648 KB Output is correct
2 Correct 62 ms 26048 KB Output is correct
3 Correct 44 ms 25652 KB Output is correct
4 Correct 21 ms 25780 KB Output is correct
5 Correct 39 ms 25912 KB Output is correct
6 Correct 105 ms 28420 KB Output is correct
7 Correct 83 ms 27496 KB Output is correct
8 Correct 93 ms 29212 KB Output is correct
9 Correct 126 ms 29212 KB Output is correct
10 Correct 84 ms 29612 KB Output is correct
11 Correct 117 ms 30112 KB Output is correct
12 Correct 114 ms 30508 KB Output is correct