oj.uz

Submission #547929

# Submission time Handle Problem Language Result Execution time Memory
547929 2022-04-12T03:22:45 Z fhvirus Synchronization (JOI13_synchronization) C++17
0 / 100
 446 ms 20408 KB 
#include <bits/stdc++.h>
using namespace std;

const int kL = 17;
const int kN = 100'001;
int N, M, Q;
int X[kN], Y[kN];
vector<int> aj[kN];

int in[kN], ou[kN], tot;
int jp[kL][kN];

void dfs(int u, int p) {
	jp[0][u] = p;
	in[u] = ++tot;
	for (const int& v: aj[u]) {
		if (v == p) continue;
		dfs(v, u);
	}
	ou[u] = tot;
}

int val[kN];
void mo(int p, int v) {
	for (; p <= N; p += p & -p)
		val[p] += v;
}
int qu(int p) {
	int r = 0;
	for (; p > 0; p -= p & -p)
		r += val[p];
	return r;
}

int gh(int u) {
	int v = qu(in[u]);
	for (int l = kL - 1; l >= 0; --l)
		if (qu(in[jp[l][u]]) == v)
			u = jp[l][u];
	return u;
}

int ans[kN], tag[kN];
bitset<kN> st;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M >> Q;

	for (int i = 1; i + 1 <= N; ++i) {
		cin >> X[i] >> Y[i];
		aj[X[i]].push_back(Y[i]);
		aj[Y[i]].push_back(X[i]);
	}

	dfs(1, 1);

	for (int l = 1; l < kL; ++l)
		for (int i = 1; i <= N; ++i)
			jp[l][i] = jp[l - 1][jp[l - 1][i]];

	for (int i = 1; i <= N; ++i) {
		mo(in[i], 1);
		mo(ou[i] + 1, -1);
	}

	fill(ans + 1, ans + N + 1, 1);
	fill(tag + 1, tag + N + 1, 1);

	for (int D, i = 1; i <= M; ++i) {
		cin >> D;
		int u = (X[D] == jp[0][Y[D]] ? Y[D] : X[D]);
		if (st[D]) {
			int h = gh(u);
			ans[u] = ans[h];
			mo(in[u], 1);
			mo(ou[u] + 1, -1);
		} else {
			mo(in[u], -1);
			mo(ou[u] + 1, 1);
			ans[gh(u)] += tag[u];
			tag[u] = 0;
		}
		st.flip(D);
	}

	for (int C, i = 1; i <= Q; ++i) {
		cin >> C;
		cout << ans[gh(C)] << '\n';
	}

	return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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