oj.uz

Submission #857204

# Submission time Handle Problem Language Result Execution time Memory
857204 2023-10-05T15:10:58 Z CongHao Inside information (BOI21_servers) C++14
100 / 100
 227 ms 30244 KB 
// [+] dinhmanhhungwillwinioi2024
#include <bits/stdc++.h>
using namespace std;

const int N = 12e4 + 5, numQ = N * 2;

vector<pair<int, int>> adj[N], Q[N];
vector<int> C[N];
char qr[numQ];
int n, q;

int ans[numQ];

bool rem[N];
int sz[N];

int dfs_size(int x, int p) {
	sz[x] = 1;
	for (const auto &elem: adj[x])
		if (elem.second != p && !rem[elem.second])
			sz[x] += dfs_size(elem.second, x);
	return sz[x];
}

int find_centroid(int x, int p, int n) {
	for (const auto &elem: adj[x])
		if (elem.second != p && !rem[elem.second] && sz[elem.second] > n / 2)
			return find_centroid(elem.second, x, n);
	return x;
}

struct FenwickTree {
	int BIT[numQ];
	vector<pair<int, int>> tmp;
	
	FenwickTree() = default;
	
	void update(int x, int w, bool reset = false) {
		if (!reset) tmp.emplace_back(x, w);
		for (; x <= q; x += x & -x)
			BIT[x] += w;
	}
	
	int pref(int x) const {
		int ans = 0;
		for (; x > 0; x -= x & -x)
			ans += BIT[x];
		return ans;
	}
	
	void reset() {
		while (!tmp.empty()) {
			auto S = tmp.back();
			tmp.pop_back();
			update(S.first, -S.second, true);
		}
	}
} fen;

int vs[N];

int rt = 0;
void dfs_calc(int x, int p, int d) { // decrease
	for (const auto &elem: Q[x]) 
		ans[elem.first] |= (vs[elem.second] && vs[elem.second] < elem.first);
	for (const int &id: C[x])
		if (id > rt) ans[id] += fen.pref(id - 1) + 1;
	for (const auto &elem: adj[x]) {
		int w, y; tie(w, y) = elem;
		if (y == p || rem[y] || d < w) continue;
		dfs_calc(y, x, w);
	}
}

vector<int> tmp;
void dfs_add(int x, int p, int d) { // increase
	vs[x] = d;
	tmp.emplace_back(x);
	fen.update(d, +1);
	for (const auto &elem: adj[x]) {
		int w, y; tie(w, y) = elem;
		if (y == p || rem[y] || d > w) continue;
		dfs_add(y, x, w);
	}
}

void centroid(int c) {
	c = find_centroid(c, 0, dfs_size(c, 0));
	rem[c] = true;
		
	for (const auto &elem: adj[c]) {
		int y, w; tie(w, y) = elem;
		if (rem[y]) continue;
		vs[c] = w;
		rt = w;
		dfs_calc(y, c, w); 
		dfs_add(y, c, w); 
	}
	
	for (const auto &elem: Q[c]) 
		ans[elem.first] |= (vs[elem.second] && vs[elem.second] < elem.first);
	for (const int &id: C[c])
		ans[id] += fen.pref(id - 1) + 1;
	
	fen.reset();
	vs[c] = 0;
	while (!tmp.empty()) {
		vs[tmp.back()] = 0;
		tmp.pop_back();
	}
	
	for (const auto &elem: adj[c]) {
		int y = elem.second;
		if (rem[y]) continue;
		centroid(y);
	}
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> q; q += n - 1;
	for (int i = 1; i <= q; i++) {
		cin >> qr[i];
		if (qr[i] == 'S') {
			int x, y;
			cin >> x >> y;
			adj[x].emplace_back(i, y);
			adj[y].emplace_back(i, x);
		} else if (qr[i] == 'Q') {
			int u, d;
			cin >> u >> d;
			if (u != d) Q[d].emplace_back(i, u);
			else ans[i] = true;
		} else {
			int d;
			cin >> d;
			C[d].emplace_back(i);
		}
	}
	for (int i = 1; i <= n; i++)
		sort(adj[i].begin(), adj[i].end(), greater<pair<int, int>>());
	centroid(1);
	for (int i = 1; i <= q; i++) {
		if (qr[i] == 'Q')
			cout << (ans[i] ? "yes" : "no") << '\n';
		else if (qr[i] == 'C')
			cout << ans[i] << '\n';
	}
	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 13656 KB Output is correct
2 Correct 26 ms 13904 KB Output is correct
3 Correct 28 ms 13792 KB Output is correct
4 Correct 29 ms 13916 KB Output is correct
5 Correct 26 ms 14172 KB Output is correct
6 Correct 24 ms 14168 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 13656 KB Output is correct
2 Correct 26 ms 13904 KB Output is correct
3 Correct 28 ms 13792 KB Output is correct
4 Correct 29 ms 13916 KB Output is correct
5 Correct 26 ms 14172 KB Output is correct
6 Correct 24 ms 14168 KB Output is correct
7 Correct 19 ms 13656 KB Output is correct
8 Correct 28 ms 14672 KB Output is correct
9 Correct 24 ms 14628 KB Output is correct
10 Correct 28 ms 14692 KB Output is correct
11 Correct 29 ms 14844 KB Output is correct
12 Correct 26 ms 14940 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13660 KB Output is correct
2 Correct 83 ms 21704 KB Output is correct
3 Correct 91 ms 21544 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13660 KB Output is correct
2 Correct 83 ms 21704 KB Output is correct
3 Correct 91 ms 21544 KB Output is correct
4 Correct 18 ms 13660 KB Output is correct
5 Correct 85 ms 24260 KB Output is correct
6 Correct 57 ms 21760 KB Output is correct
7 Correct 66 ms 22188 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13656 KB Output is correct
2 Correct 143 ms 25612 KB Output is correct
3 Correct 136 ms 25620 KB Output is correct
4 Correct 130 ms 26740 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13656 KB Output is correct
2 Correct 143 ms 25612 KB Output is correct
3 Correct 136 ms 25620 KB Output is correct
4 Correct 130 ms 26740 KB Output is correct
5 Correct 19 ms 13660 KB Output is correct
6 Correct 148 ms 29188 KB Output is correct
7 Correct 139 ms 30244 KB Output is correct
8 Correct 141 ms 28512 KB Output is correct
9 Correct 130 ms 28496 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13656 KB Output is correct
2 Correct 123 ms 20188 KB Output is correct
3 Correct 125 ms 19028 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13656 KB Output is correct
2 Correct 123 ms 20188 KB Output is correct
3 Correct 125 ms 19028 KB Output is correct
4 Correct 19 ms 13804 KB Output is correct
5 Correct 142 ms 23868 KB Output is correct
6 Correct 107 ms 22500 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13660 KB Output is correct
2 Correct 158 ms 25424 KB Output is correct
3 Correct 145 ms 25644 KB Output is correct
4 Correct 145 ms 26656 KB Output is correct
5 Correct 18 ms 13660 KB Output is correct
6 Correct 115 ms 20156 KB Output is correct
7 Correct 105 ms 19084 KB Output is correct
8 Correct 140 ms 20304 KB Output is correct
9 Correct 116 ms 19908 KB Output is correct
10 Correct 170 ms 22832 KB Output is correct
11 Correct 147 ms 22100 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13660 KB Output is correct
2 Correct 158 ms 25424 KB Output is correct
3 Correct 145 ms 25644 KB Output is correct
4 Correct 145 ms 26656 KB Output is correct
5 Correct 18 ms 13660 KB Output is correct
6 Correct 115 ms 20156 KB Output is correct
7 Correct 105 ms 19084 KB Output is correct
8 Correct 140 ms 20304 KB Output is correct
9 Correct 116 ms 19908 KB Output is correct
10 Correct 170 ms 22832 KB Output is correct
11 Correct 147 ms 22100 KB Output is correct
12 Correct 19 ms 13668 KB Output is correct
13 Correct 159 ms 29188 KB Output is correct
14 Correct 157 ms 30156 KB Output is correct
15 Correct 133 ms 28500 KB Output is correct
16 Correct 136 ms 28548 KB Output is correct
17 Correct 19 ms 14680 KB Output is correct
18 Correct 134 ms 23756 KB Output is correct
19 Correct 108 ms 22336 KB Output is correct
20 Correct 153 ms 23632 KB Output is correct
21 Correct 143 ms 23376 KB Output is correct
22 Correct 153 ms 25428 KB Output is correct
23 Correct 192 ms 26060 KB Output is correct
24 Correct 191 ms 25544 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13656 KB Output is correct
2 Correct 25 ms 13916 KB Output is correct
3 Correct 24 ms 13660 KB Output is correct
4 Correct 32 ms 14180 KB Output is correct
5 Correct 25 ms 14424 KB Output is correct
6 Correct 24 ms 14172 KB Output is correct
7 Correct 19 ms 13656 KB Output is correct
8 Correct 94 ms 21644 KB Output is correct
9 Correct 109 ms 21632 KB Output is correct
10 Correct 19 ms 13660 KB Output is correct
11 Correct 136 ms 25532 KB Output is correct
12 Correct 139 ms 25648 KB Output is correct
13 Correct 126 ms 26748 KB Output is correct
14 Correct 18 ms 13656 KB Output is correct
15 Correct 129 ms 20088 KB Output is correct
16 Correct 106 ms 19040 KB Output is correct
17 Correct 112 ms 20308 KB Output is correct
18 Correct 108 ms 19788 KB Output is correct
19 Correct 143 ms 22868 KB Output is correct
20 Correct 157 ms 22132 KB Output is correct
21 Correct 93 ms 21068 KB Output is correct
22 Correct 94 ms 20636 KB Output is correct
23 Correct 94 ms 19792 KB Output is correct
24 Correct 134 ms 19840 KB Output is correct
25 Correct 130 ms 23764 KB Output is correct
26 Correct 108 ms 18004 KB Output is correct
27 Correct 105 ms 17744 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13656 KB Output is correct
2 Correct 25 ms 13916 KB Output is correct
3 Correct 24 ms 13660 KB Output is correct
4 Correct 32 ms 14180 KB Output is correct
5 Correct 25 ms 14424 KB Output is correct
6 Correct 24 ms 14172 KB Output is correct
7 Correct 19 ms 13656 KB Output is correct
8 Correct 94 ms 21644 KB Output is correct
9 Correct 109 ms 21632 KB Output is correct
10 Correct 19 ms 13660 KB Output is correct
11 Correct 136 ms 25532 KB Output is correct
12 Correct 139 ms 25648 KB Output is correct
13 Correct 126 ms 26748 KB Output is correct
14 Correct 18 ms 13656 KB Output is correct
15 Correct 129 ms 20088 KB Output is correct
16 Correct 106 ms 19040 KB Output is correct
17 Correct 112 ms 20308 KB Output is correct
18 Correct 108 ms 19788 KB Output is correct
19 Correct 143 ms 22868 KB Output is correct
20 Correct 157 ms 22132 KB Output is correct
21 Correct 93 ms 21068 KB Output is correct
22 Correct 94 ms 20636 KB Output is correct
23 Correct 94 ms 19792 KB Output is correct
24 Correct 134 ms 19840 KB Output is correct
25 Correct 130 ms 23764 KB Output is correct
26 Correct 108 ms 18004 KB Output is correct
27 Correct 105 ms 17744 KB Output is correct
28 Correct 20 ms 13660 KB Output is correct
29 Correct 27 ms 14684 KB Output is correct
30 Correct 26 ms 14384 KB Output is correct
31 Correct 37 ms 14668 KB Output is correct
32 Correct 36 ms 15008 KB Output is correct
33 Correct 26 ms 14656 KB Output is correct
34 Correct 20 ms 14680 KB Output is correct
35 Correct 94 ms 24076 KB Output is correct
36 Correct 54 ms 21700 KB Output is correct
37 Correct 63 ms 21896 KB Output is correct
38 Correct 27 ms 14684 KB Output is correct
39 Correct 157 ms 29156 KB Output is correct
40 Correct 139 ms 30152 KB Output is correct
41 Correct 156 ms 28656 KB Output is correct
42 Correct 149 ms 28568 KB Output is correct
43 Correct 20 ms 14484 KB Output is correct
44 Correct 131 ms 23864 KB Output is correct
45 Correct 118 ms 22352 KB Output is correct
46 Correct 129 ms 23688 KB Output is correct
47 Correct 139 ms 23380 KB Output is correct
48 Correct 227 ms 25340 KB Output is correct
49 Correct 216 ms 26060 KB Output is correct
50 Correct 174 ms 25492 KB Output is correct
51 Correct 79 ms 22668 KB Output is correct
52 Correct 81 ms 22728 KB Output is correct
53 Correct 60 ms 22472 KB Output is correct
54 Correct 60 ms 22936 KB Output is correct
55 Correct 64 ms 21692 KB Output is correct
56 Correct 105 ms 22144 KB Output is correct
57 Correct 123 ms 25100 KB Output is correct
58 Correct 140 ms 22200 KB Output is correct
59 Correct 108 ms 21332 KB Output is correct