oj.uz

Submission #5051

# Submission time Handle Problem Language Result Execution time Memory
5051 2014-01-29T20:28:40 Z cki86201 Shymbulak (IZhO14_shymbulak) C++
100 / 100
 88 ms 14240 KB 
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
#include<set>
#include<ctype.h>
using namespace std;

#define X first
#define Y second
typedef long long ll;
typedef pair<int,int> Pi;

int st[200020], en[400040], nxt[400040];
int N;
int cycle[200020];
int ind[200020];
int down[200020];
int dp[200020][5];
int cycle_sz;
int L;
ll ans;

void addedge(int s,int e,int c){nxt[c]=st[s],st[s]=c,en[c]=e;}

int Que[200020];

void dfs_cycle(int x,int fa,int num)
{
	if(num == cycle_sz)return;
	cycle[num] = x;
	for(int i=st[x];i;i=nxt[i])if(ind[en[i]] == 2 && en[i]!=fa)dfs_cycle(en[i],x,num+1);
}

struct Deque{
	Pi p[200020];
	int f,r;
	void init(){f=r=0;}
	void push(Pi x){
		while(f!=r&&p[f-1].X<x.X)f--;
		if(p[f-1].X == x.X)p[f-1].Y += x.Y;
		else p[f++]=x;
	}
	inline void pop(Pi x){
		if(p[r].X==x.X)p[r].Y -= x.Y;
		if(!p[r].Y)r++;
	}
	inline Pi read(){return p[r];}
};

void bfs()
{
	int *fr = Que, *re = Que, i;
	for(i=1;i<=N;i++)dp[i][1] = 1;
	for(i=1;i<=N;i++)if(ind[i] == 1){
		*fr++ = i;
		dp[i][4] = 1;
	}
	while(fr!=re){
		int t = *re++;
		for(i=st[t];i;i=nxt[i]){
			if(ind[en[i]]){
				int &a = dp[en[i]][0], &b = dp[en[i]][2];
				if(!a || a < dp[t][0]+1){
					b = a, dp[en[i]][3] = dp[en[i]][1];
					a = dp[t][0]+1, dp[en[i]][1] = dp[t][1];
					dp[en[i]][4] = 1;
				}
				else if(a==dp[t][0]+1)dp[en[i]][1] += dp[t][1], dp[en[i]][4]++;
				else if(!b || dp[t][0]+1 > b)dp[en[i]][3] = dp[t][3], b = dp[t][0]+1;
				else if(dp[t][0]+1 == b)dp[en[i]][3] += dp[t][3];
				ind[t]--, ind[en[i]]--;
				if(ind[en[i]] == 1)*fr++ = en[i];
			}
		}
	}
	for(i=1;i<=N;i++)if(ind[i] == 2)cycle_sz++;
	for(i=1;i<=N;i++)if(ind[i] == 2){
		dfs_cycle(i,-1,0);
		break;
	}
}

void solve(){
	Deque Dq;
	int i;
	for(i=1;i<=N;i++){
		if(dp[i][4] != 1)L = max(L, dp[i][0]*2);
		else L = max(L, dp[i][0] + dp[i][2]);
	}
	Dq.init();
	int half = cycle_sz>>1;
	for(i=0;i<half;i++){
		Dq.push(Pi(i + dp[cycle[i]][0], dp[cycle[i]][1]));
	}
	for(i=0;i<cycle_sz;i++){
		int e = (i+half) % cycle_sz;
		Dq.push(Pi(i + half + dp[cycle[e]][0], dp[cycle[e]][1]));
		Dq.pop(Pi(i + dp[cycle[i]][0], dp[cycle[i]][1]));
		Pi tmp = Dq.read();
		int len = tmp.X - i + dp[cycle[i]][0];
		if(L < len)ans = (ll)dp[cycle[i]][1] * tmp.Y, L = len;
		else if(L == len)ans += (ll)dp[cycle[i]][1] * tmp.Y;
	}
	for(i=1;i<=N;i++){
		if(dp[i][4]!=1 && L==dp[i][0]*2){
			ll tmp = (ll)dp[i][1] * dp[i][1];
			for(int j=st[i];j;j=nxt[j]){
				if(ind[i]==2 && ind[en[j]]==2)continue;
				if(dp[en[j]][0] + 1 == dp[i][0])tmp -= (ll)dp[en[j]][1] * dp[en[j]][1];
			}
			ans += tmp/2;
		}
		if(dp[i][4]==1 && L==dp[i][0] + dp[i][2])ans += (ll)dp[i][1] * dp[i][3];
	}
	printf("%lld",ans);
}

int main()
{
	scanf("%d",&N);
	int i;
	for(i=1;i<=N;i++){
		int x, y;
		scanf("%d%d",&x,&y);
		addedge(x,y,i<<1);
		addedge(y,x,i<<1|1);
		ind[x]++, ind[y]++;
	}
	bfs();
	solve();
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13460 KB Output is correct
2 Correct 0 ms 13464 KB Output is correct
3 Correct 0 ms 13460 KB Output is correct
4 Correct 0 ms 13460 KB Output is correct
5 Correct 0 ms 13460 KB Output is correct
6 Correct 0 ms 13460 KB Output is correct
7 Correct 0 ms 13464 KB Output is correct
8 Correct 0 ms 13460 KB Output is correct
9 Correct 0 ms 13456 KB Output is correct
10 Correct 0 ms 13464 KB Output is correct
11 Correct 0 ms 13464 KB Output is correct
12 Correct 0 ms 13460 KB Output is correct
13 Correct 0 ms 13460 KB Output is correct
14 Correct 0 ms 13464 KB Output is correct
15 Correct 0 ms 13464 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13464 KB Output is correct
2 Correct 36 ms 13464 KB Output is correct
3 Correct 28 ms 14240 KB Output is correct
4 Correct 32 ms 13460 KB Output is correct
5 Correct 28 ms 13464 KB Output is correct
6 Correct 88 ms 13460 KB Output is correct
7 Correct 68 ms 13464 KB Output is correct
8 Correct 60 ms 13464 KB Output is correct
9 Correct 60 ms 13460 KB Output is correct
10 Correct 64 ms 13464 KB Output is correct
11 Correct 64 ms 13460 KB Output is correct
12 Correct 68 ms 13464 KB Output is correct