oj.uz

Submission #549303

# Submission time Handle Problem Language Result Execution time Memory
549303 2022-04-15T15:10:07 Z sidon Synchronization (JOI13_synchronization) C++17
0 / 100
 262 ms 24636 KB 
#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 <= N; i += i&-i) v += F[i];
	return v;
}

void add(int i, int v) {
	for(; i >= 1; 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Incorrect 2 ms 2676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 20556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 262 ms 24636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2768 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -