oj.uz

Submission #549317

# Submission time Handle Problem Language Result Execution time Memory
549317 2022-04-15T15:21:40 Z sidon Synchronization (JOI13_synchronization) C++17
100 / 100
 269 ms 24592 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 >= 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 17 ms 4100 KB Output is correct
8 Correct 15 ms 4052 KB Output is correct
9 Correct 15 ms 4052 KB Output is correct
10 Correct 252 ms 17680 KB Output is correct
11 Correct 263 ms 17672 KB Output is correct
12 Correct 258 ms 23820 KB Output is correct
13 Correct 102 ms 17524 KB Output is correct
14 Correct 170 ms 17112 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 18504 KB Output is correct
2 Correct 128 ms 20360 KB Output is correct
3 Correct 128 ms 23252 KB Output is correct
4 Correct 123 ms 23148 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2680 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 18 ms 4820 KB Output is correct
8 Correct 249 ms 24516 KB Output is correct
9 Correct 269 ms 24592 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 21820 KB Output is correct
2 Correct 152 ms 24240 KB Output is correct
3 Correct 149 ms 24412 KB Output is correct
4 Correct 149 ms 24396 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2684 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 4 ms 2820 KB Output is correct
6 Correct 17 ms 4224 KB Output is correct
7 Correct 262 ms 18436 KB Output is correct
8 Correct 260 ms 24588 KB Output is correct
9 Correct 125 ms 18704 KB Output is correct
10 Correct 204 ms 18332 KB Output is correct
11 Correct 156 ms 21728 KB Output is correct
12 Correct 145 ms 21792 KB Output is correct
13 Correct 174 ms 24364 KB Output is correct