oj.uz

Submission #13168

# Submission time Handle Problem Language Result Execution time Memory
13168 2015-02-01T11:16:18 Z woqja125 Shymbulak (IZhO14_shymbulak) C++14
12 / 100
 133 ms 30504 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 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);
	printf("%lld", solve());
	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 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 max = 0, tm;
	long long maxC = 0, 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 22480 KB Output is correct
2 Incorrect 0 ms 22480 KB Output isn't correct
3 Incorrect 0 ms 22480 KB Output isn't correct
4 Correct 0 ms 22480 KB Output is correct
5 Incorrect 0 ms 22480 KB Output isn't correct
6 Incorrect 0 ms 22480 KB Output isn't correct
7 Incorrect 3 ms 22480 KB Output isn't correct
8 Correct 0 ms 22480 KB Output is correct
9 Incorrect 0 ms 22480 KB Output isn't correct
10 Incorrect 0 ms 22480 KB Output isn't correct
11 Correct 0 ms 22480 KB Output is correct
12 Incorrect 0 ms 22480 KB Output isn't correct
13 Incorrect 3 ms 22480 KB Output isn't correct
14 Incorrect 3 ms 22480 KB Output isn't correct
15 Correct 0 ms 22480 KB Output is correct

Subtask #2
2.0 / 20.0

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

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 25644 KB Output isn't correct
2 Incorrect 55 ms 26044 KB Output isn't correct
3 Incorrect 53 ms 25648 KB Output isn't correct
4 Incorrect 25 ms 25776 KB Output isn't correct
5 Incorrect 44 ms 25908 KB Output isn't correct
6 Incorrect 126 ms 28416 KB Output isn't correct
7 Incorrect 88 ms 27492 KB Output isn't correct
8 Incorrect 83 ms 29208 KB Output isn't correct
9 Incorrect 115 ms 29208 KB Output isn't correct
10 Incorrect 89 ms 29608 KB Output isn't correct
11 Incorrect 100 ms 30108 KB Output isn't correct
12 Incorrect 133 ms 30504 KB Output isn't correct