Submission #255535

#	Time	Username	Problem	Language	Result	Execution time	Memory
255535		oolimry	Synchronization (JOI13_synchronization)	C++14	100 / 100	372 ms	26360 KiB

synchronization

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using namespace std;
typedef pair<int,int> ii;

int n, m, Q;
ii edges[100005];
bool open[100005];

vector<int> adj[100005];
int low[100005];
int high[100005];
int cnt = 0;

int p[100005][20];
void dfs(int u, int P){
	p[u][0] = P;
	for(int i = 1;i <= 19;i++) p[u][i] = p[p[u][i-1]][i-1];
	low[u] = cnt; high[u] = cnt; cnt++;
	
	for(int v : adj[u]){
		if(v == P) continue;
		dfs(v, u);
		high[u] = max(high[u], high[v]);
	}
}

int tree[200010];
void update(int l, int r, int v){
	for(l += n, r += n;l < r;l >>= 1, r >>= 1){
		if(l&1) tree[l++] += v;
		if(r&1) tree[--r] += v;
	}
}

int query(int i){
	int res = 0;
	for(i += n;i > 0;i >>= 1) res += tree[i];
	return res;
}

void disconnect(int u) { update(low[u], high[u]+1, 1); }
void connect(int u) { update(low[u], high[u]+1, -1); }
int findRoot(int u){
	for(int i = 19;i >= 0;i--){
		int nxt = p[u][i];
		if(nxt != 0 && query(low[nxt]) == query(low[u])) u = nxt;
	}
	return u;
}

int ans[100005]; ///how much stuff in there
int last[100005]; ///how much stuff previous time

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);	
	cin >> n >> m >> Q;
	
	for(int i = 1;i < n;i++){
		int u, v; cin >> u >> v;
		edges[i] = ii(u,v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	dfs(1,0);
	
	for(int i = 1;i <= n;i++){
		disconnect(i);
		ans[i] = 1;
	}
	
	while(m--){
		int e; cin >> e;
		int u = edges[e].first, v = edges[e].second;
		if(p[v][0] == u) swap(u,v); ///u will be child of v;
		
		if(!open[e]){ ///activate edge
			open[e] = true;
			ans[findRoot(v)] += ans[u] - last[u];
			connect(u);
		}
		else{ ///disactivate edge
			open[e] = false;
			ans[u] = last[u] = ans[findRoot(v)];
			disconnect(u);
		}
	}
	
	while(Q--){
		int u; cin >> u;
		cout << ans[findRoot(u)] << '\n';
	}
}

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