Submission #968661

#	Time	Username	Problem	Language	Result	Execution time	Memory
968661		Lecorbio	Synchronization (JOI13_synchronization)	C++17	100 / 100	309 ms	26964 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, dist[N], tin[N], tout[N], up[N][P], val[N], last[N], tree[B*2];
pair<int,int> edge[N];
vector<int> g[N];
bool active[N];

void dfs(int v, int par){
	tin[v] = ++timer;
	val[v] = 1;
	up[v][0] = par;
	for (int i=1; i<P; i++) up[v][i] = up[up[v][i-1]][i-1];
	for (auto u : g[v]){
		if (u == par) continue;
		dist[u] = dist[v] + 1;
		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 x = query(tin[v]);
	for (int i=P-1; i>=0; i--){
		if (query(tin[up[v][i]]) == x) v = up[v][i];
	}
	return v;
}

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);
	}
	
	dist[1] = 1;
	dfs(1, 1);
	for (int i=1; i<=n; i++) tree[tin[i]+B] = -dist[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);
		
		if (!active[x]){
			val[find_root(b)] += val[a] - last[a];
			update(1, 0, B-1, tin[a], tout[a], 1);
			active[x] = true;
		}else{
			val[a] = last[a] = val[find_root(b)];
			update(1, 0, B-1, tin[a], tout[a], -1);
			active[x] = false;
		}
	}
	
	for (int i=0; i<q; i++){
		int v; cin >> v;
		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: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40