oj.uz

Submission #13180

# Submission time Handle Problem Language Result Execution time Memory
13180 2015-02-01T13:31:16 Z woqja125 Shymbulak (IZhO14_shymbulak) C++14
0 / 100
 134 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-i <= CC-j; j++);
	for(i=0; i<CC; i++)
	{
		get(tm, tmc, i+1, j);
		add(max, maxC, max, maxC, tm-i+cn(i), tmc*cd(i));
		j++;
	}
	return maxC;
}

Subtask #1
10.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 Incorrect 0 ms 22484 KB Output isn't correct
4 Correct 3 ms 22484 KB Output is correct
5 Incorrect 0 ms 22484 KB Output isn't correct
6 Incorrect 0 ms 22484 KB Output isn't correct
7 Incorrect 3 ms 22484 KB Output isn't correct
8 Correct 0 ms 22484 KB Output is correct
9 Incorrect 3 ms 22484 KB Output isn't correct
10 Incorrect 0 ms 22484 KB Output isn't correct
11 Correct 0 ms 22484 KB Output is correct
12 Incorrect 0 ms 22484 KB Output isn't correct
13 Incorrect 0 ms 22484 KB Output isn't correct
14 Incorrect 0 ms 22484 KB Output isn't correct
15 Correct 0 ms 22484 KB Output is correct

Subtask #2
4.0 / 20.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 Incorrect 0 ms 22484 KB Output isn't correct
4 Incorrect 2 ms 22484 KB Output isn't correct
5 Incorrect 0 ms 22616 KB Output isn't correct
6 Incorrect 2 ms 22616 KB Output isn't correct
7 Correct 0 ms 22616 KB Output is correct
8 Incorrect 3 ms 22616 KB Output isn't correct
9 Incorrect 5 ms 22616 KB Output isn't correct
10 Incorrect 3 ms 22616 KB Output isn't correct

Subtask #3
8.333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 25648 KB Output is correct
2 Incorrect 60 ms 26048 KB Output isn't correct
3 Incorrect 46 ms 25652 KB Output isn't correct
4 Incorrect 41 ms 25780 KB Output isn't correct
5 Incorrect 49 ms 25912 KB Output isn't correct
6 Correct 69 ms 28420 KB Output is correct
7 Incorrect 97 ms 27496 KB Output isn't correct
8 Incorrect 82 ms 29212 KB Output isn't correct
9 Incorrect 100 ms 29212 KB Output isn't correct
10 Incorrect 80 ms 29612 KB Output isn't correct
11 Incorrect 96 ms 30112 KB Output isn't correct
12 Incorrect 117 ms 30508 KB Output isn't correct