oj.uz

Submission #5114

# Submission time Handle Problem Language Result Execution time Memory
5114 2014-02-08T22:28:37 Z cki86201 Synchronization (JOI13_synchronization) C++
100 / 100
 4276 ms 16808 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];
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12240 KB Output is correct
2 Correct 0 ms 12240 KB Output is correct
3 Correct 0 ms 12240 KB Output is correct
4 Correct 0 ms 12240 KB Output is correct
5 Correct 0 ms 12240 KB Output is correct
6 Correct 0 ms 12240 KB Output is correct
7 Correct 68 ms 12240 KB Output is correct
8 Correct 68 ms 12240 KB Output is correct
9 Correct 72 ms 12240 KB Output is correct
10 Correct 4172 ms 12240 KB Output is correct
11 Correct 4176 ms 12240 KB Output is correct
12 Correct 1432 ms 16808 KB Output is correct
13 Correct 1040 ms 12240 KB Output is correct
14 Correct 2672 ms 12240 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 792 ms 14460 KB Output is correct
2 Correct 756 ms 14428 KB Output is correct
3 Correct 788 ms 16808 KB Output is correct
4 Correct 768 ms 16796 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12240 KB Output is correct
2 Correct 0 ms 12240 KB Output is correct
3 Correct 0 ms 12240 KB Output is correct
4 Correct 0 ms 12240 KB Output is correct
5 Correct 0 ms 12240 KB Output is correct
6 Correct 0 ms 12240 KB Output is correct
7 Correct 40 ms 12580 KB Output is correct
8 Correct 1468 ms 16800 KB Output is correct
9 Correct 1492 ms 16800 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1524 ms 16804 KB Output is correct
2 Correct 816 ms 16768 KB Output is correct
3 Correct 800 ms 16804 KB Output is correct
4 Correct 800 ms 16804 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12240 KB Output is correct
2 Correct 0 ms 12240 KB Output is correct
3 Correct 0 ms 12240 KB Output is correct
4 Correct 0 ms 12240 KB Output is correct
5 Correct 0 ms 12240 KB Output is correct
6 Correct 72 ms 12240 KB Output is correct
7 Correct 4276 ms 12240 KB Output is correct
8 Correct 1452 ms 16804 KB Output is correct
9 Correct 1036 ms 12240 KB Output is correct
10 Correct 2664 ms 12240 KB Output is correct
11 Correct 804 ms 14460 KB Output is correct
12 Correct 804 ms 14456 KB Output is correct
13 Correct 792 ms 16800 KB Output is correct