Submission #1078414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078414		nishkarsh	Synchronization (JOI13_synchronization)	C++14	100 / 100	246 ms	28584 KiB

synchronization

#include <bits/stdc++.h>
#define ll long long
#define vt vector
#define pb push_back
using namespace std;

int fastexp(int b, int e, int mod){
	int ans = 1;
	while(e){
		if(e&1) ans = (1ll*ans*b)%mod;
		b = (1ll*b*b)%mod;
		e >>= 1;
	}
	return ans;
}

const int N = 2e5+1;
const int mod = 998244353;
const ll INFLL = 1e18;
const int INF = 2e9;
const int logn = 20;

int fenwick[N];

void update(int ind, int val){
	while(ind < N){
		fenwick[ind] += val;
		ind += ind&(-ind);
	}
}

int query(int ind){
	int ans = 0;
	while(ind > 0){
		ans += fenwick[ind];
		ind = ind&(ind-1);
	}
	return ans;
}


int edges[N], lt[N], rt[N], par[N][logn], on[N], curr_val[N], edge_val[N];
vt<int> adj[N];
int node_cnt;

void dfs(int u, int p){
	lt[u] = ++node_cnt;
	par[u][0] = p;
	for(int v : adj[u]){
		if((u^edges[v]) == p) edges[v] = u;
		else dfs(u^edges[v], u);
	}
	rt[u] = ++node_cnt;
}

int find_ances(int u){
	for(int i = logn-1; i >= 0; i--){
		if(query(lt[par[u][i]]) == query(lt[u])) u = par[u][i];
	}
	return u;
}

void on_edge(int i){
	int u = edges[i];
	int v = par[u][0];
	int ances = find_ances(v);
	curr_val[v] = curr_val[ances];
	int new_num = curr_val[u] + curr_val[v] - edge_val[i];
	curr_val[ances] = curr_val[u] = curr_val[v] = new_num;
	update(lt[u], -1); update(rt[u], 1);
}

void off_edge(int i){
	int u = edges[i];
	int ances = find_ances(u);
	curr_val[u] = curr_val[par[u][0]] = edge_val[i] = curr_val[ances];
	update(lt[u], 1); update(rt[u], -1);
}

void solve(){
	int n,m,q,u,v;
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		edges[i] = u^v;
		adj[u].pb(i);
		adj[v].pb(i);
	}

	dfs(1,1);

	for(int j = 1; j < logn; j++) for(int i = 1; i <= n; i++) par[i][j] = par[par[i][j-1]][j-1];

	for(int i = 1; i <= n; i++){
		update(lt[i], 1), update(rt[i], -1);
		curr_val[i] = 1;
	}

	while(m--){
		cin >> u;
		on[u] ^= 1;
		if(on[u]) on_edge(u);
		else off_edge(u);
	}

	for(int i = 1; i < n; i++) if(on[i]) off_edge(i);

	while(q--){
		cin >> u;
		cout << curr_val[u] << "\n";
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t = 1;
	// cin >> t;

	while(t--) solve();

	return 0;
}

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