Submission #446482

#	Time	Username	Problem	Language	Result	Execution time	Memory
446482		Millad	Synchronization (JOI13_synchronization)	C++14	100 / 100	646 ms	26940 KiB

synchronization

//In the name of god
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define debug(x) cout << #x << " : " << x << "\n"
#define use_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef string str;

const ll maxn = 2e5 + 5;
bool act[maxn];
ll n, m, q, fen[maxn], a[maxn], c[maxn], par[20][maxn], h[maxn];
ll t = 1, tin[maxn], tout[maxn];
pll p[maxn];
vector <ll> adj[maxn];
void add(int p, int x){
	for(; p; p -= (p & -p))fen[p] = (fen[p] + x);
}
int get(int p){
	int sum = 0;
	for(p ++; p < maxn; p += (p & -p))sum = (sum + fen[p]);
	return sum;
}
void dfs(ll v){
	tin[v] = t ++;
	for(ll j = 1; j < 19; j ++){
		ll u = par[j - 1][v];
		if((u == 0) || (par[j - 1][u] == 0))break;
		par[j][v] = par[j - 1][u];
	}
	for(ll j : adj[v]){
		if(j == par[0][v])continue;
		h[j] = h[v] + 1;
		par[0][j] = v;
		dfs(j);
	}
	tout[v] = t;
}
ll get_root(ll v){
	for(ll i = 18; i >= 0; i --){
		if(par[i][v] == 0)continue;
		if(get(tin[par[i][v]]) != get(tin[v]))continue;
		v = par[i][v];
	}
	return v;
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m >> q;
	for(ll i = 1; i < n; i ++){
		cin >> p[i].F >> p[i].S;
		adj[p[i].F].pb(p[i].S);
		adj[p[i].S].pb(p[i].F);
	}
	dfs(1);
	for(ll i = 1; i <= n; i ++){
		add(tin[i], -1);
		add(tout[i], 1);
		a[i] = 1;
	}
	for(ll i = 1; i < n; i ++){
		if(h[p[i].F] > h[p[i].S]){
			swap(p[i].F, p[i].S);
		}
	}
	while(m --){
		ll ind; cin >> ind;
		ll root = get_root(p[ind].F);
		if(act[ind]){
			a[p[ind].S] = a[root];
			c[p[ind].S] = a[root];
			add(tin[p[ind].S], -1);
			add(tout[p[ind].S], 1);
		}
		else{
			a[root] += a[p[ind].S] - c[p[ind].S];
			add(tin[p[ind].S], 1);
                        add(tout[p[ind].S], -1);
		}
		act[ind] = 1 - act[ind];
	}
	while(q --){
		ll v; cin >> v;
		v = get_root(v);
		cout << a[v] << '\n';
	}
}

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