oj.uz

Submission #49902

# Submission time Handle Problem Language Result Execution time Memory
49902 2018-06-04T14:05:30 Z tmwilliamlin168 Synchronization (JOI13_synchronization) C++14
100 / 100
 390 ms 20908 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=1e5;
int n, m, q, x[mxN-1], y[mxN-1], st[mxN], en[mxN], dt, ft[mxN+1], v[mxN], lc[mxN-1], anc[mxN][17];
vector<int> adj[mxN];

inline void upd(int i, int x) {
	for(++i; i<=n; i+=i&-i)
		ft[i]+=x;
}

inline int qry(int i) {
	int r=0;
	for(++i; i; i-=i&-i)
		r+=ft[i];
	return r;
}

void dfs(int u, int p) {
	st[u]=dt++;
	anc[u][0]=p;
	for(int i=1; i<17; ++i)
		anc[u][i]=anc[u][i-1]==-1?-1:anc[anc[u][i-1]][i-1];
	for(int v : adj[u])
		if(v!=p)
			dfs(v, u);
	en[u]=dt;
}

inline int find(int x) {
	int a=qry(st[x]), b=x;
	for(int i=16; i>=0; --i)
		if(anc[b][i]!=-1&&qry(st[anc[b][i]])==a)
			b=anc[b][i];
	return b;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> q;
	for(int i=0; i<n-1; ++i) {
		cin >> x[i] >> y[i], --x[i], --y[i];
		adj[x[i]].push_back(y[i]);
		adj[y[i]].push_back(x[i]);
	}
	dfs(0, -1);
	for(int i=0; i<n; ++i) {
		v[i]=1;
		upd(st[i], 1);
		upd(en[i], -1);
	}
	for(int i=0; i<n-1; ++i)
		if(anc[x[i]][0]==y[i])
			swap(x[i], y[i]);
	while(m--) {
		int dj;
		cin >> dj, --dj;
		int x2=find(x[dj]);
		if(lc[dj]==-1) {
			upd(st[y[dj]], 1);
			upd(en[y[dj]], -1);
			lc[dj]=v[y[dj]]=v[x2];
		} else {
			upd(st[y[dj]], -1);
			upd(en[y[dj]], 1);
			v[x2]+=v[y[dj]]-lc[dj];
			lc[dj]=-1;
		}
	}
	while(q--) {
		int ck;
		cin >> ck, --ck;
		cout << v[find(ck)] << "\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2788 KB Output is correct
3 Correct 4 ms 2788 KB Output is correct
4 Correct 5 ms 2880 KB Output is correct
5 Correct 5 ms 2924 KB Output is correct
6 Correct 5 ms 3216 KB Output is correct
7 Correct 17 ms 4160 KB Output is correct
8 Correct 17 ms 4200 KB Output is correct
9 Correct 15 ms 4220 KB Output is correct
10 Correct 334 ms 15612 KB Output is correct
11 Correct 349 ms 15812 KB Output is correct
12 Correct 390 ms 20092 KB Output is correct
13 Correct 146 ms 20092 KB Output is correct
14 Correct 233 ms 20092 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 20092 KB Output is correct
2 Correct 104 ms 20092 KB Output is correct
3 Correct 134 ms 20092 KB Output is correct
4 Correct 115 ms 20092 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20092 KB Output is correct
2 Correct 4 ms 20092 KB Output is correct
3 Correct 4 ms 20092 KB Output is correct
4 Correct 4 ms 20092 KB Output is correct
5 Correct 4 ms 20092 KB Output is correct
6 Correct 11 ms 20092 KB Output is correct
7 Correct 22 ms 20092 KB Output is correct
8 Correct 375 ms 20348 KB Output is correct
9 Correct 382 ms 20448 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 20448 KB Output is correct
2 Correct 189 ms 20788 KB Output is correct
3 Correct 201 ms 20908 KB Output is correct
4 Correct 215 ms 20908 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20908 KB Output is correct
2 Correct 4 ms 20908 KB Output is correct
3 Correct 4 ms 20908 KB Output is correct
4 Correct 4 ms 20908 KB Output is correct
5 Correct 6 ms 20908 KB Output is correct
6 Correct 27 ms 20908 KB Output is correct
7 Correct 365 ms 20908 KB Output is correct
8 Correct 390 ms 20908 KB Output is correct
9 Correct 119 ms 20908 KB Output is correct
10 Correct 218 ms 20908 KB Output is correct
11 Correct 135 ms 20908 KB Output is correct
12 Correct 134 ms 20908 KB Output is correct
13 Correct 232 ms 20908 KB Output is correct