Submission #521372

#	Time	Username	Problem	Language	Result	Execution time	Memory
521372		amunduzbaev	Synchronization (JOI13_synchronization)	C++14	100 / 100	253 ms	23404 KiB

synchronization

#include "bits/stdc++.h"
using namespace std;
 
#define ar array

const int N = 1e5 + 5;
struct BIT{
	int tree[N];
	void add(int i, int v){ 
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int get(int i){
		int c = 0;
		for(;i>0;i-=(i&-i)) c += tree[i];
		return c;
	}
	
	int get(int l, int r){
		return get(r) - get(l - 1);
	}
}tree;

vector<int> edges[N];
int tin[N], tout[N], t, par[N][17];
int pre[N], is[N], cnt[N];

void dfs(int u, int p = -1){
	tin[u] = ++t, par[u][0] = p;
	for(int j=1;j<17;j++) par[u][j] = par[par[u][j-1]][j-1];
	for(auto x : edges[u]){
		if(x == p) continue;
		dfs(x, u);
	} tout[u] = t;
}

int get(int u){
	for(int j=16;~j;j--){
		if(tree.get(tin[par[u][j]]) == tree.get(tin[u])){
			u = par[u][j];
		}
	} return u;
}

void merge(int a, int b, int in){
	if(par[b][0] == a) swap(a, b);
	
	b = get(b);
	tree.add(tin[a], -1), tree.add(tout[a] + 1, 1);
	cnt[b] = cnt[b] + cnt[a] - pre[in];
}

void split(int a, int b, int in){
	if(par[b][0] == a) swap(a, b);
	
	b = get(b);
	tree.add(tin[a], 1), tree.add(tout[a] + 1, -1);
	pre[in] = cnt[a] = cnt[b];
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m, k; cin>>n>>m>>k;
	vector<ar<int, 2>> e(n);
	for(int i=1;i<n;i++){
		cin>>e[i][0]>>e[i][1];
		edges[e[i][0]].push_back(e[i][1]);
		edges[e[i][1]].push_back(e[i][0]);
	}
	dfs(1, 1);
	for(int i=1;i<=n;i++){ cnt[i] = 1;
		tree.add(tin[i], 1), tree.add(tout[i] + 1, -1);
	}
	
	for(int i=0;i<m;i++){
		int j; cin>>j;
		if(is[j]){
			is[j] = 0;
			split(e[j][0], e[j][1], j);
		} else {
			is[j] = 1;
			merge(e[j][0], e[j][1], j);
		}
	}
	
	for(int i=1;i<n;i++) if(is[i]) split(e[i][0], e[i][1], i);
	while(k--){
		int u; cin>>u;
		cout<<cnt[u]<<"\n";
	}
}

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