Submission #549317

#	Time	Username	Problem	Language	Result	Execution time	Memory
549317		sidon	Synchronization (JOI13_synchronization)	C++17	100 / 100	269 ms	24592 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
 
const int Z = 1e5+2, B = 17;
 
int N, M, Q, last[Z], L[Z], R[Z], p[Z][B], ans[Z], dfsTimer;
array<int, 2> h[Z];
bool state[Z];
vector<int> g[Z];
 
void dfs(int u) {
	L[u] = ++dfsTimer;
	for(int i = 0; i + 1 < B; ++i)
		p[u][i+1] = p[p[u][i]][i];
	for(const int &v : g[u]) if(v != p[u][0])
		p[v][0] = u, dfs(v);
	R[u] = 1+dfsTimer;
}
 
int F[Z];
 
int get(int i) {
	int v = 0;
	for(; i >= 1; i -= i&-i) v += F[i];
	return v;
}
 
void add(int i, int v) {
	for(; i <= N; i += i&-i) F[i] += v;
}
 
int find(int u) {
	int x = get(L[u]);
	for(int i = B; i--; ) {
		int y = get(L[p[u][i]]);
		if(x - y == 1<<i)
			x = y, u = p[u][i];
	}
	return u;
}
 
void modify(int d) {
	auto [u, v] = h[d];
	if(v == p[u][0]) swap(u, v);
	int w = find(u);
 
	if(state[d] ^= 1) {
		ans[w] += ans[v] - last[d];
		add(L[v], +1);
		add(R[v], -1);
	} else {
		last[d] = ans[v] = ans[w];
		add(L[v], -1);
		add(R[v], +1);
	}
}
 
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M >> Q;
 
	for(int i = 0; i + 1 < N; ++i) {
		auto &[u, v] = h[i];
		cin >> u >> v; --u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(0);
	fill(ans, ans + N, 1);
 
	while(M--) {
		int d; cin >> d;
		modify(d - 1);
	}
	for(int i = 0; i + 1 < N; ++i) if(state[i])
		modify(i);
 
	while(Q--) {
		int u; cin >> u;
		cout << ans[u-1] << '\n';
	}
}

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