제출 #547898

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
547898		8e7	동기화 (JOI13_synchronization)	C++17	100 / 100	481 ms	23660 KiB

synchronization

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct BIT{
	int bit[maxn*2];
	void modify(int ind, int val) {
		ind++;
		for (;ind < maxn*2;ind += ind & (-ind)) bit[ind] += val;
	}
	int query(int ind) {
		ind++;
		int ret = 0;
		for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
		return ret;
	}
} bit;
vector<int> adj[maxn];
pii ed[maxn];
int anc[17][maxn], dep[maxn], comp[maxn], lef[maxn*2], rig[maxn*2];
int ans[maxn], dif[maxn];
vector<int> ord;
int ti = 1;
void dfs(int n, int par, int d) {
	anc[0][n] = par;
	dep[n] = d;
	ord.push_back(n);
	lef[n] = ti++;
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n, d+1);
		}
	}
	rig[n] = ti++;
}
int jump(int a, int x) {
	int cnt = 0;
	while (x) {
		if (x & 1) a = anc[cnt][a];
		x >>= 1;
	}
	return a;
}

int main() {
	io
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1;i <= n - 1;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		ed[i] = {u, v};
	}	
	dfs(1, 0, 0);			
	for (int i = 1;i < 17;i++) {
		for (int j = 1;j <= n;j++) anc[i][j] = anc[i-1][anc[i-1][j]];
	}
	for (int i = 1;i <= n - 1;i++) {
		if (dep[ed[i].ff] > dep[ed[i].ss]) swap(ed[i].ff, ed[i].ss);
	}	
	for (int i = 1;i <= n;i++) {
		bit.modify(lef[i], 1), bit.modify(rig[i], -1);
		comp[i] = 1;
		dif[i] = 1;
		ans[i] = 1;
	}
	while (m--) {
		int id;
		cin >> id;
		int u = ed[id].ff, v = ed[id].ss;
		int head = u, sum = bit.query(lef[u]);
		for (int i = 16;i >= 0;i--) {
			if (!anc[i][head]) continue;
			if (bit.query(lef[anc[i][head]]) == sum) {
				head = anc[i][head];
			}	
		}
		//debug(head, v, sum);
		if (comp[v]) {
			dif[head] += dif[v];
			ans[head] += dif[v];
			bit.modify(lef[v], -1);
			bit.modify(rig[v], 1);
			dif[v] = 0;
			comp[v] = 0;
		} else {
			dif[v] = 0;
			ans[v] = ans[head];	
			bit.modify(lef[v], 1);
			bit.modify(rig[v], -1);
			comp[v] = 1;
		}
	}	
	for (int i:ord) {
		if (!comp[i]) ans[i] = ans[anc[0][i]];
	}
	while (q--) {
		int x; cin >> x;
		cout << ans[x] << '\n';
	}
}

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