oj.uz

Submission #264453

# Submission time Handle Problem Language Result Execution time Memory
264453 2020-08-14T07:00:42 Z ruler Synchronization (JOI13_synchronization) C++14
100 / 100
 617 ms 23844 KB 
// IOI 2021
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
 
////////////////////////////////////////////////////////////////////

const int N = 1e5 + 2, LG = 18;

int E[N << 1][2], M[N << 1], FEN[N], P[LG][N], ST[N], FT[N], DW[N], UP[N], t;
vector<int> G[N];

void Add(int p, int x) { for (p++; p < N; p += p & -p) FEN[p] += x; }
void Add(int l, int r, int x) { Add(l, x), Add(r, - x); }
int Get(int p) {
	int res = 0;
	for (; p; p -= p & -p) res += FEN[p];
	return res;
}
int Cnt(int v) { return Get(ST[v] + 1); }
void DFS(int v, int p = 0) {
	ST[v] = t++, P[0][v] = p, DW[v] = 1;
	for (int i = 1; i < LG; i++) P[i][v] = P[i - 1][P[i - 1][v]];
	for (int u : G[v]) if (u != p) DFS(u, v);
	FT[v] = t;
}
int GetRoot(int v) {
	int cnt = Cnt(v);
	for (int i = LG - 1; i >= 0; i--)
		if (P[i][v] != 0 && cnt == Cnt(P[i][v])) v = P[i][v];
	return v;
}

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));

	int n, m, q; cin >> n >> m >> q;
	for (int i = 1; i < n; i++) {
		int v, u; cin >> v >> u;
		G[v].push_back(u), G[u].push_back(v);
		E[i][0] = v, E[i][1] = u;
	}
	DFS(1);
	for (int i = 2; i <= n; i++) Add(ST[i], FT[i], +1);
	for (int i = 1; i < n; i++) if (P[0][E[i][1]] == E[i][0]) swap(E[i][0], E[i][1]);
	while (m--) {
		int i; cin >> i;
		int v = E[i][0], u = E[i][1];
		if (M[i]) {
			Add(ST[v], FT[v], + 1);
			DW[v] = UP[v] = DW[GetRoot(u)];
		} else {
			Add(ST[v], FT[v], -1);
			DW[GetRoot(u)] += DW[v] - UP[v];
		}
		M[i] ^= 1;
	}
	while (q--) {
		int v; cin >> v;
		cout << DW[GetRoot(v)] << endl;
	}

	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2816 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 2 ms 2816 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct
6 Correct 4 ms 2944 KB Output is correct
7 Correct 15 ms 4352 KB Output is correct
8 Correct 18 ms 4352 KB Output is correct
9 Correct 17 ms 4352 KB Output is correct
10 Correct 324 ms 18424 KB Output is correct
11 Correct 369 ms 18424 KB Output is correct
12 Correct 544 ms 23056 KB Output is correct
13 Correct 96 ms 18416 KB Output is correct
14 Correct 214 ms 17400 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 20344 KB Output is correct
2 Correct 92 ms 20092 KB Output is correct
3 Correct 111 ms 22136 KB Output is correct
4 Correct 113 ms 22136 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2868 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 2 ms 2816 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct
6 Correct 3 ms 3072 KB Output is correct
7 Correct 24 ms 4864 KB Output is correct
8 Correct 595 ms 23800 KB Output is correct
9 Correct 569 ms 23796 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 23796 KB Output is correct
2 Correct 195 ms 23196 KB Output is correct
3 Correct 177 ms 23292 KB Output is correct
4 Correct 178 ms 23288 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 3 ms 2816 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 3 ms 3072 KB Output is correct
6 Correct 18 ms 4480 KB Output is correct
7 Correct 399 ms 19320 KB Output is correct
8 Correct 617 ms 23844 KB Output is correct
9 Correct 131 ms 19416 KB Output is correct
10 Correct 294 ms 18700 KB Output is correct
11 Correct 125 ms 21500 KB Output is correct
12 Correct 123 ms 21548 KB Output is correct
13 Correct 213 ms 23288 KB Output is correct