Submission #968617

#	Time	Username	Problem	Language	Result	Execution time	Memory
968617		Lecorbio	Synchronization (JOI13_synchronization)	C++17	0 / 100	339 ms	22308 KiB

synchronization

#include <bits/stdc++.h>
#define fi first
#define se second
#define sajz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5+7, P = 20, B = 1<<17;
int n, m, q, timer = -1, tin[N], tout[N], up[N][P]; 
int val[N], last[N], ind[N], tree[B*2];
pair<int,int> edge[N];
vector<int> g[N];
bool active[N];

void dfs(int v, int par){
	up[v][0] = par;
	for (int i=1; i<P; i++) up[v][i] = up[up[v][i-1]][i-1];
	tin[v] = ++timer;
	val[v] = 1;
	for (auto u : g[v]){
		if (u == par) continue;
		dfs(u, v);
	}
	tout[v] = timer;
}

void update(int v, int a, int b, int p, int k, int x){
	if (a > k || b < p) return;
	else if (a >= p && b <= k){
		tree[v] += x;
		return;
	}
	int mid = (a+b) / 2;
	update(v*2, a, mid, p, k, x); update(v*2+1, mid+1, b, p, k, x);
}
int query(int v){
	v += B;
	int res = 0;
	while (v){
		res += tree[v];
		v /= 2;
	}
	return res;
}

int find_root(int v){
	int u = v;
	for (int i=P-1; i>=0; i--){
		if (query(tin[up[u][i]]) == query(tin[v]) && query(tin[v]) > 0) u = up[u][i];
	}
	if (active[ind[u]]) return up[u][0];
	return u;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m >> q;
    for (int i=1; i<n; i++){
		int a, b; cin >> a >> b;
		edge[i] = {a, b};
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	dfs(1, 1);
	for (int i=1; i<n; i++){
		auto [a, b] = edge[i];
		if (tin[b] > tin[a]) swap(a, b);
		ind[a] = i;
	}
	
	for (int i=0; i<m; i++){
		int x; cin >> x;
		auto [a, b] = edge[x];
		if (tin[b] > tin[a]) swap(a, b);
		
		//cout << "active: " << active[x] << " ----\n";
		//cout << a << ' ' << b << ": " << find_root(a) << '\n';
		//cout << val[a] << ' ' << val[b] << ": " << val[find_root(a)] << '\n';
		
		if (!active[x]){
			active[x] = true;
			val[find_root(a)] += val[a] - last[a];
			update(1, 0, B-1, tin[a], tout[a], 1);
		}else{
			val[a] = last[a] = val[find_root(a)];
			update(1, 0, B-1, tin[a], tout[a], -1);
			active[x] = false;
		}
		
		//cout << "val: " << val[find_root(a)] << '\n';
	}
	
	for (int i=0; i<q; i++){
		int v; cin >> v;
		//cout << v << ": " << find_root(v) << '\n';
		cout << val[find_root(v)] << '\n';
	}
 
    return 0;
}
/*

5 6 3
1 2
1 3
2 4
2 5
1
2
1
4
4
3
1
4
5

*/

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