Submission #1276785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276785		g4yuhg	Synchronization (JOI13_synchronization)	C++20	100 / 100	315 ms	19064 KiB

synchronization

//Huyduocdithitp
#include<bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll, ll>
#define N 200005
using namespace std;

const ll inf = 1e9;

bool ghuy4g;

vector<ll> adj[N];
pii canh[N];

ll n, m, q, par[N], st[4 * N];

ll sz[N], pos[N], tour[N], chain_head[N], chain_id[N], high[N];
ll cur_pos = 1, cur_chain = 1;

void update(ll id, ll l, ll r, ll i, ll v) {
	if (i > r || i < l) return;
	if (l == r) {
		st[id] = v;
		return;
	}
	ll mid = (l + r) / 2;
	update(id * 2, l, mid, i, v);
	update(id * 2 + 1, mid + 1, r, i, v);
	st[id] = max(st[id * 2], st[id * 2 + 1]);
}

ll get(ll id, ll l, ll r, ll L, ll R) {
	if (l > R || r < L) return -inf;
	if (L <= l && r <= R) {
		return st[id];
	}
	ll mid = (l + r) / 2;
	return max(get(id * 2, l, mid, L, R), get(id * 2 + 1, mid + 1, r, L, R));
}

void dfs(ll u, ll parent) {
	sz[u] = 1;
	for (auto v : adj[u]) {
		if (v == parent) continue;
		par[v] = u;
		high[v] = high[u] + 1;
		dfs(v, u);
		sz[u] += sz[v];
	}
}

ll lca(ll u, ll v) {
	while (chain_id[u] != chain_id[v]) {
		//cout << u << " " << v << " " << chain_id[u] << " " << chain_id[v] << endl;
		//cout << chain_head[chain_id[u]] << " " << chain_head[chain_id[v]] << endl;
		if (high[chain_head[chain_id[u]]] > high[chain_head[chain_id[v]]]) {
			u = par[chain_head[chain_id[u]]];
		}
		else {
			v = par[chain_head[chain_id[v]]];
		}
	}
	if (high[u] < high[v]) return u;
	return v;
}

ll qr(ll u, ll v) {
	//return 1;
	ll res = -inf;
	ll x = lca(u, v);
	//return 1;
	while (chain_id[u] != chain_id[x]) {
		ll r = chain_head[chain_id[u]];
		res = max(res, get(1, 1, n, pos[r], pos[u]));
		u = par[r];
	}
	while (chain_id[v] != chain_id[x]) {
		ll r = chain_head[chain_id[v]];
		res = max(res, get(1, 1, n, pos[r], pos[v]));
		v = par[r];
	}
	if (high[u] < high[v]) {
		res = max(res, get(1, 1, n, pos[u], pos[v]));
	}
	else {
		res = max(res, get(1, 1, n, pos[v], pos[u]));
	}
	return res;
}

void hld(ll u, ll parent) {
	if (chain_head[cur_chain] == 0) {
		//cout << "head " << chain_id[u] << " " << u << endl;
		chain_head[cur_chain] = u;
	}
	pos[u] = cur_pos;
	tour[cur_pos] = u;
	chain_id[u] = cur_chain;
	//cout << u << " chain " << cur_chain << endl;
	cur_pos ++ ;
	ll nxt = 0;
	for (auto v : adj[u]) {
		if (v == parent) continue;
		if (sz[v] > sz[nxt]) {
			nxt = v;
		}
	}
	if (nxt) {
		hld(nxt, u);
	}
	for (auto v : adj[u]) {
		if (v == parent || v == nxt) continue;
		cur_chain ++ ;
		hld(v, u);
	}
}

void build(ll id, ll l, ll r) {
	if (l == r) {
		st[id] = l;
		return;
	}
	ll mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	st[id] = max(st[id * 2], st[id * 2 + 1]);
}

void pre() {
	dfs(1, 1);
	cur_chain = cur_pos = 1;
	hld(1, 1);
	build(1, 1, n);
	for (int i = 1; i <= n - 1; i ++) {
		if (par[canh[i].fi] == canh[i].se) {
			swap(canh[i].fi, canh[i].se);
		}
	}
}

ll find(ll u) {
	//cout << "find " << u << endl;
	ll x = qr(1, u);
	/*if (x != qr(u, 1)) {
		cout << "ngu";
		exit(3);
	}*/
	if (x == -inf) return 1;
	return tour[x];
}

ll a[N], c[N];
bool is[N];

void solve() {
	for (int i = 1; i <= m; i ++) {
		ll id;
		cin >> id;
		ll u = canh[id].fi, v = canh[id].se;
		if (is[id] == 0) {
			// noi u v
			ll ru = find(u); // rv == v
			ll moi = a[ru] + a[v] - c[v];
			//cout << u << " " << v << " ru " << ru << " " << moi << endl;
			update(1, 1, n, pos[v], -inf);
			a[ru] = moi;
		}
		else {
			ll ru = find(u);
			a[v] = c[v] = a[ru];
			//cout << "go ra " << ru << " " << v << " a[v] " << a[v] << endl;
			update(1, 1, n, pos[v], pos[v]);
		}
		is[id] = 1 - is[id];
	}
	for (int i = 1; i <= q; i ++) {
		ll u; cin >> u;
		cout << a[find(u)] << endl;
	}
}

bool klinh;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> q;
	for (int i = 1; i <= n - 1; i ++) {
		a[i] = 1; a[i + 1] = 1;
		ll u, v;
		cin >> u >> v;
		canh[i] = {u, v};
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	pre();
	solve();
	
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
	
	return 0;
}

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