Submission #5051

#	Time	Username	Problem	Language	Result	Execution time	Memory
5051		cki86201	Shymbulak (IZhO14_shymbulak)	C++98	100 / 100	88 ms	14240 KiB

shymbulak

#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 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50