Submission #409112

#	Time	Username	Problem	Language	Result	Execution time	Memory
409112		vuhoanggiap	Synchronization (JOI13_synchronization)	C++17	100 / 100	368 ms	25444 KiB

synchronization

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

const int maxN = 1e5 + 5, maxM = 2e5 + 5;  
int n, m, q; 
vector<int> adj[maxN]; 

int A[maxM], B[maxM]; 
bool state[maxM]; 

int euler; 
int s[maxN], e[maxN]; 
int jump[maxN][22]; 

void dfs(int u, int p) {
	s[u] = ++euler; 
	jump[u][0] = p; 
	for(int i = 1; i < 20; i++) 
		jump[u][i] = jump[jump[u][i - 1]][i - 1]; 
	for(auto v : adj[u])
		if(v != p)
			dfs(v, u); 
	e[u] = euler; 
}

int fen[maxN]; 
void update(int i, int val) { while(i <= n + 1) fen[i] += val, i += (i & (-i)); }
int query(int i) { int ret = 0; while(i) ret += fen[i], i -= (i & (-i)); return ret; }

int ancestor(int u) {
	int oldu = u; 
	for(int i = 19; i >= 0; i--) 
		if(query(s[oldu]) == query(s[jump[u][i]]))
			u = jump[u][i]; 
	return u; 
}

int distinct[maxN], distinctUp[maxN]; 
int ans[maxN]; 

signed main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> q; 
	for(int i = 1; i < n; i++) {
		cin >> A[i] >> B[i]; 
		adj[A[i]].pb(B[i]); 
		adj[B[i]].pb(A[i]); 
	} 
	dfs(1, 1);
	for(int i = 1; i <= n; i++) {
		distinct[i] = 1; 
		update(s[i], 1); 
		update(e[i] + 1, -1); 
	}
	for(int i = 1; i < n; i++) 
		if(jump[A[i]][0] == B[i])
			swap(A[i], B[i]); 
	for(int i = 1; i <= m; i++) {
		int id; cin >> id; 
		if(!state[id]) {
			int u = ancestor(A[id]); 
			distinct[u] += distinct[B[id]] - distinctUp[B[id]]; 
			update(s[B[id]], -1); 
			update(e[B[id]] + 1, 1); 
		}
		else {
			int u = ancestor(A[id]); 
			distinct[B[id]] = distinctUp[B[id]] = distinct[u]; 
			update(s[B[id]], 1); 
			update(e[B[id]] + 1, -1); 
		}
		state[id] ^= 1; 
	}
	for(int i = 1; i <= n; i++) {
		ans[i] = distinct[ancestor(i)]; 
 	}
 	for(int i = 1; i <= q; i++) {
 		int u; cin >> u; 
 		cout << ans[u] << '\n'; 
 	}
}

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