Submission #5114

#	Time	Username	Problem	Language	Result	Execution time	Memory
5114		cki86201	Synchronization (JOI13_synchronization)	C++98	100 / 100	4276 ms	16808 KiB

synchronization

#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];
void addE(int s,int e,int c){nxt[c]=st[s],st[s]=c,en[c]=e;}

int N, M, Q, cq;
int in[700][2];
int w[200020], L[200020];
int ue[200020], uv[200020];
int S[200020], D[200020], ns = 1;
int dep[200020], un[200020], up[200020];
bool con[200020];

void dfs(int x,int f)
{
	S[x] = ns;
	w[x] = 1;
	up[x] = x;
	for(int i=st[x];i;i=nxt[i]){
		if(en[i] == f)continue;
		ue[en[i]] = i>>1, uv[en[i]] = x;
		dep[en[i]] = dep[x] + 1;
		dfs(en[i], x);
	}
	D[x] = ns++;
}

inline bool c_ances(int x,int y){return S[x]<=D[y]&&D[y]<=D[x];}

int par(int a,int t)
{
	int i, ret = up[a];
	while(un[ret])ret = un[ret];
	for(i=0;i<t;i++){
		if(!con[ue[in[i][1]]] && c_ances(in[i][1], a) && dep[ret] < dep[in[i][1]])ret = in[i][1];
	}
	return ret;
}

void cut(int t)
{
	int a = in[t][0], b = in[t][1];
	int p = par(a,t);
	L[ue[b]] = w[b] = w[p];
	un[b] = p;
}

void link(int t)
{
	int a = in[t][0], b = in[t][1];
	int p = par(a,t);
	w[p] += w[b] - L[ue[b]];
	un[b] = p;
}

void dfs2(int x,int p,int f)
{
	un[x] = 0;
	w[x] = w[p];
	up[x] = p;
	for(int i=st[x];i;i=nxt[i]){
		if(en[i] == f)continue;
		if(con[i>>1])dfs2(en[i],p,x);
		else dfs2(en[i],en[i],x);
	}
}

void solve(int n)
{
	for(int i=0;i<n;i++){
		if(con[ue[in[i][1]]])cut(i);
		else link(i);
		con[ue[in[i][1]]] ^= 1;
	}
	dfs2(1,1,-1);
}

int main()
{
	scanf("%d%d%d",&N,&M,&Q);
	int i;
	for(i=1;i<N;i++){
		int x, y;
		scanf("%d%d",&x,&y);
		addE(x,y,i<<1);
		addE(y,x,i<<1|1);
	}
	dfs(1,-1);
	int counter = 0;
	cq = (int)sqrt(M);
	for(i=1;i<=M;i++){
		int t,x,y;
		scanf("%d",&t);
		x = en[t<<1], y = en[t<<1|1];
		if(uv[x] == y)swap(x,y);
		in[counter][0] = x, in[counter][1] = y;
		if(++counter == cq || i == M)solve(counter), counter = 0;
	}
	for(i=1;i<=Q;i++){
		int x;
		scanf("%d",&x);
		printf("%d\n",w[x]);
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40