Submission #1260431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260431		nlsosad	Synchronization (JOI13_synchronization)	C++20	100 / 100	216 ms	45880 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
vector<int> a[100001], tr[800001];
int depth[100001], state[100001], cnt[100001], f[100001], mx[100001], p[100001], r[100001];
pair<int, int> edge[100001];
vector<pair<int, int>> change;
int find(int x){
	if(p[x]==x){
		return x;
	}else return find(p[x]);
}
void unite(int u, int v){
	int ru = find(u), rv = find(v);
	if(ru!=rv){
		change.push_back({ru, rv});
		int tmp = mx[ru] + mx[rv] - f[v];
		mx[ru] = mx[rv] = tmp;
		if(r[ru] > r[rv]){
			p[rv] = ru;
			r[ru] += r[rv];
		}else{
			p[ru] = rv;
			r[rv] += r[ru];
		}
	}
}
void undo(){
	auto [u, v] = change.back();
	change.pop_back();
	int tmp = max(mx[u], mx[v]);
	mx[u] = mx[v] = tmp;
	if(r[u] > r[v]){
		r[u]-=r[v];
	}else r[v]-=r[u];
	p[u] = u;
	p[v] = v;
}

void dfs(int u, int p){
	for (int v:a[u]){
		if(v!=p){
			depth[v] = depth[u] + 1;
			dfs(v, u);
		}
	}
}
void add(int node, int start, int end, int l, int r, int id){
	if(start > r or end < l){
		return;
	}
	if(l<=start and end<=r){
		tr[node].push_back(id);
		return;
	}
	int mid = (start+end)/2;
	add(2*node, start, mid, l, r, id);
	add(2*node+1, mid+1, end, l, r, id);
}
void query(int node, int start, int end){
	for (int id:tr[node]){
		auto [u, v] = edge[id];
		if(depth[u] > depth[v])swap(u, v);
		unite(u, v);
	}
	if(start!=end){
		int mid = (start+end)/2;
		query(2*node, start, mid);
		query(2*node+1, mid+1, end);
	}
	for (int id:tr[node]){
		auto [u,v] = edge[id];
		if(depth[u] > depth[v])swap(u,v);
		f[v] = mx[find(v)];
		undo();
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i =1;i<n;++i){
		int u, v;
		cin >> u >> v;
		edge[i] = {u, v};
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for (int i =1;i<=n;++i){
		mx[i] = 1;
		r[i] = 1, p[i] = i;
	}
	dfs(1, 0);
	for (int i = 1;i<=m;++i){
		int id;
		cin >> id;
		if(state[id]==0){
			state[id] = i;
		}else{
			add(1, 1, m, state[id], i-1, id);
			state[id] = 0;
		}
	}
	for (int i = 1;i<n;++i){
		if(state[i]){
			add(1, 1, m, state[i], m, i);
			state[i] = 0;
		}
	}
	query(1, 1, m);
	while(q--){
		int u;
		cin >> u;
		cout << mx[find(u)] << '\n';
	}
}

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