Submission #1277896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277896		nanaseyuzuki	Synchronization (JOI13_synchronization)	C++20	100 / 100	261 ms	22012 KiB

synchronization

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703 
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 3e5 + 5, inf = 1e9;

int n, m, q, d[mn], sz[mn], par[mn], heavy[mn], st[mn], ft[mn], euler[mn], head[mn], timer = 0;
vector <int> a[mn];

void dfs(int u, int p){
	sz[u] = 1;
	for(auto v : a[u]){
		if(v == p) continue;
		d[v] = d[u] + 1; 
		par[v] = u;
		dfs(v, u);
		sz[u] += sz[v];
		if(sz[v] > sz[heavy[u]]) heavy[u] = v;
	}
	ft[u] = timer;
}

void decompose(int u, int h){
	head[u] = h;
	st[u] = ++ timer;
	euler[timer] = u;
	if(heavy[u]) decompose(heavy[u], h);
	for(auto v : a[u]){
		if(v != par[u] && v != heavy[u]) decompose(v, v);
	}
	ft[u] = timer;
}

int node[mn << 2];

void build(int id, int l, int r){
	if(l == r){
		node[id] = l;
		return;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	node[id] = max(node[id << 1], node[id << 1 | 1]);
}

void update(int id, int l, int r, int pos, int val){
	if(l > pos || r < pos) return;
	if(l == r){
		node[id] = val;
		return;
	}
	int mid = (l + r) >> 1;
	update(id << 1, l, mid, pos, val);
	update(id << 1 | 1, mid + 1, r, pos, val);
	node[id] = max(node[id << 1], node[id << 1 | 1]);
}

int get(int id, int l, int r, int u, int v){
	if(l > v || r < u) return - inf;
	if(l >= u && r <= v) return node[id];
	int mid = (l + r) >> 1;
	return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));	
}

int qr(int u, int v){
	int res = - inf;
	while(head[u] != head[v]){
		if(d[par[head[u]]] > d[par[head[v]]]){
			res = max(res, get(1, 1, n, st[head[u]], st[u]));
			u = par[head[u]];
		}
		else{
			res = max(res, get(1, 1, n, st[head[v]], st[v]));
			v = par[head[v]];
		}
	}
	res = max(res, get(1, 1, n, min(st[u], st[v]), max(st[u], st[v])));
	return euler[res];
}

int on[mn], neww[mn], old[mn];
pii e[mn];

void solve(){
    cin >> n >> m >> q;
	for(int i = 1; i < n; i++){
		int u, v; cin >> u >> v;
		e[i] = {u, v};
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for(int i = 1; i <= n; i++) old[i] = 0, neww[i] = 1;
	dfs(1, 0);
	decompose(1, 1);
	build(1, 1, n);
	for(int i = 1; i <= n; i++) if(e[i].se == par[e[i].fi]) swap(e[i].fi, e[i].se);

	for(int i = 1; i <= m; i++){
		int t; cin >> t;
		auto [u, v] = e[t];
		if(!on[t]){
			int root = qr(1, u);
			// cout << root << '\n';
			// cout << "bat " << u << ' ' << root << '\n';
			neww[root] += neww[v] - old[v];
			// cout << "bye " << v << '\n';
			update(1, 1, n, st[v], - inf);
		}
		else{
			int root = qr(1, u);
			// cout << root << '\n';
			// cout << "tat " << u << ' ' << root << '\n';
			neww[v] = neww[root], old[v] = neww[root];
			// cout << "hello " << v << '\n';
			update(1, 1, n, st[v], st[v]);
		}
		on[t] ^= 1;
	}
	for(int i = 1; i <= q; i++){
		int x; cin >> x;
		cout << neww[qr(1, x)] << '\n';
	}
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

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