Submission #478295

#	Time	Username	Problem	Language	Result	Execution time	Memory
478295		amunduzbaev	동기화 (JOI13_synchronization)	C++14	100 / 100	302 ms	28096 KiB

synchronization

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

#define ar array

const int N = 2e5 + 5;
vector<int> edges[N];
int tin[N], tout[N], t = 1, par[N][20], res[N];

struct BIT{
	int tree[N];
	void add(int i, int v){
		for(++i; i < N; i += (i & -i)) tree[i] += v;
	}
	
	int get(int i){
		int rr = 0;
		for(++i; i; i -= (i & -i)) rr += tree[i];
		return rr;
	}
}tree;

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

int find(int x){
	int v = tree.get(tin[x]);
	for(int i=19;~i;i--){
		if(par[x][i] && tree.get(tin[par[x][i]]) == v) x = par[x][i];
	}
	
	return x;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0); 

	int n, m, q; cin>>n>>m>>q;
	vector<ar<int, 2>> ee(n);
	for(int i=1;i<n;i++){
		cin>>ee[i][0]>>ee[i][1];
		edges[ee[i][0]].push_back(ee[i][1]);
		edges[ee[i][1]].push_back(ee[i][0]);
	}
	
	dfs(1);
	for(int i=1;i<=n;i++) res[i] = 1;
	for(int i=1;i<n;i++){
		if(par[ee[i][0]][0] == ee[i][1]){
			swap(ee[i][0], ee[i][1]);
		}
	}
	vector<int> is(n);
	while(m--){
		int i; cin>>i;
		int par = find(ee[i][0]);
		if(is[i] == -1){
			tree.add(tin[ee[i][1]], 1);
			tree.add(tout[ee[i][1]], -1);
			is[i] = res[ee[i][1]] = res[par];
		} else {
			tree.add(tin[ee[i][1]], -1);
			tree.add(tout[ee[i][1]], 1);
			res[par] += res[ee[i][1]] - is[i];
			is[i] = -1;
		}
	}
	
	while(q--){
		int u; cin>>u;
		cout<<res[find(u)]<<"\n";
	}
}

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