제출 #379432

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379432		reymontada61	동기화 (JOI13_synchronization)	C++14	100 / 100	2577 ms	28268 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;

int n, m, q;
const int MXN = 100005, MXK = 20;
vector<int> adj[MXN];

int par[MXN][MXK];

int eda[MXN], edb[MXN];
int depth[MXN];
int st_start[MXN], st_end[MXN];

int ti = 1;

void dfs(int node, int pa, int dep) {
	depth[node] = dep;
	par[node][0] = pa;
	st_start[node] = ti;
	ti++;
	for (int i=1; i<MXK; i++) {
		par[node][i] = par[par[node][i-1]][i-1];
	}
	for (auto x: adj[node]) {
		if (x == pa) continue;
		dfs(x, node, dep+1);
	}
	st_end[node] = ti;
	ti++;
}

int seg[MXN * 8];

void add(int ind, int l, int r, int pos, int by) {
	if (l == r) {
		seg[ind] += by;
		return;
	}
	int m = (l + r) / 2;
	if (pos <= m) add(ind*2, l, m, pos, by);
	else add(ind*2+1, m+1, r, pos, by);
	seg[ind] = seg[ind*2] + seg[ind*2+1];
}

int query(int ind, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) return seg[ind];
	if (ql > r || qr < l) return 0;
	int m = (l + r) / 2;
	return query(ind*2, l, m, ql, qr) + query(ind*2+1, m+1, r, ql, qr);
}

int kth(int n, int k) {
	for (int i=0; i<MXK; i++) {
		if (k & (1 << i)) n = par[n][i];
	}
	return n;
}

int path(int x, int y) {
	return query(1, 1, 2*n, 1, st_start[y]) - query(1, 1, 2*n, 1, st_start[x]);
}

int truepar(int x) {
	int ans = x;
	for (int i=MXK-1; i>=0; i--) {
		if (path(par[ans][i], x) == (depth[x] - depth[par[ans][i]])) {
			ans = par[ans][i];
		}
	}
	return ans;
}

bool built[MXN];
int ans[MXN], c[MXN];

signed main() {

	cin >> n >> m >> q;
	for (int i=1; i<=n-1; i++) {
		int a, b;
		cin >> a >> b;
		eda[i] = a;
		edb[i] = b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i=1; i<=n; i++) {
		ans[i] = 1;
	}
	
	for (int i=0; i<MXN; i++) for (int j=0; j<MXK; j++) par[i][j] = 1;
	
	dfs(1, 1, 0);
	
	while (m--) {
		int x;
		cin >> x;
		
		int a = eda[x], b = edb[x];
		if (depth[a] > depth[b]) swap(a, b);
		
		if (built[x]) {
			ans[b] = c[b] = ans[truepar(a)];
			add(1, 1, 2*n, st_start[b], -1);
			add(1, 1, 2*n, st_end[b], 1);
		}
		else {
			ans[truepar(a)] += ans[b] - c[b];
			add(1, 1, 2*n, st_start[b], 1);
			add(1, 1, 2*n, st_end[b], -1);
		}
		built[x] = !built[x];
		
		
	}
	
	while (q--) {
		int j;
		cin >> j;
		cout << ans[truepar(j)] << endl;
	}

}

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