oj.uz

Submission #528470

# Submission time Handle Problem Language Result Execution time Memory
528470 2022-02-20T10:49:08 Z iliaM Inside information (BOI21_servers) C++17
100 / 100
 563 ms 57372 KB 
#include <bits/stdc++.h>
using namespace std;
#define cerr cerr << "DEBUG "

constexpr int N = 3e5 + 10;

int n, k;
vector<pair<int, int>> qp[N];
vector<int> qu[N];
vector<pair<int, int>> up, down;
vector<int> verts;
int sz[N];
vector<pair<int, int>> g[N];
bool used[N];
long long ans[N];
int mark[N];
pair<int, int> tmp[N];
bool has[N];

int centroid(int v, int p, int m) {
	has[v] = true;
	verts.push_back(v);
	int ret = 0, cool = 1;
	sz[v] = 1;
	for (auto &e : g[v]) {
		int u = e.first;
		if (u != p && !used[u]) {
			ret ^= ~centroid(u, v, m);
			cool &= sz[u] <= m / 2;
			sz[v] += sz[u];
		}
	}
	return cool && m - sz[v] <= m / 2 ? v : ~ret;
}


void dfs(int v, int p, int fe, int f, int s) {
	sz[v] = 1;
	if (~f) {
		for (auto &query : qu[v]) {
			if (fe > query) {
				continue;
			}
			up.push_back({fe, query});
		}
		mark[v] = fe;
	}
	if (~s) {
		down.push_back({fe, s});
		tmp[v] = make_pair(fe, s);
		assert(s >= fe);
	}
	for (auto &e : g[v]) {
		int u = e.first, w = e.second;
		if (u != p && !used[u]) {
			dfs(u, v, fe, f == -1 || w >= f ? -1 : w, s == -1 || w <= s ? -1 : w);
			sz[v] += sz[u];
		}
	}
}

int fen[N];

void update(int i, int x) {
	for (++i; i < N; i += i & -i) {
		fen[i] += x;
	}
}

int query(int i) {
	int ret = 0;
	for (++i; i > 0; i -= i & -i) {
		ret += fen[i];
	}
	return ret;
}

void solve() {
	static vector<int> vec[N];
	auto &a = up, &b = down;
	for (int i = 0; i < (int) b.size(); ++i) {
		vec[i].clear();
	}

	for (auto &x : a) {
		auto p = upper_bound(b.begin(), b.end(), make_pair(x.first, INT_MAX));
		ans[x.second]++; // for centroid
		if (p != b.end()) {
			vec[p - b.begin()].push_back(x.second);
		}
	}

	for (int i = (int) b.size() - 1; i >= 0; --i) {
		update(b[i].second, +1);
		for (auto &x : vec[i]) {
			ans[x] += query(x);
		}
	}
	for (auto &x : b) {
		update(x.second, -1);
	}
}

void decompose(int v, int m) {
	int cent = centroid(v, -1, m);
	
	up.clear();
	down.clear();
	
	sz[cent] = 1;
	for (auto &e : g[cent]) {
		int u = e.first, w = e.second;
		if (!used[u]) {
			dfs(u, cent, w, w, w);
			sz[cent] += sz[u];
		}
	}
	
	// calc for pairs in subtrees
	sort(down.begin(), down.end());
	solve();
	
	assert((int) verts.size() == sz[cent]);

	for (auto &u : verts) {
		for (auto &query : qp[u]) {
			if (!has[query.first]) {
				continue;
			}
			if (u == cent) {
				ans[query.second] += query.first == u ||
					(tmp[query.first].second < query.second);
			} else if (~mark[u]) {
				if (query.first == cent) {
					ans[query.second] += mark[u] < query.second;
				} else {
					ans[query.second] += mark[u] < tmp[query.first].first &&
						tmp[query.first].second < query.second;
				}
			}
		}
	}

	// calc for pairs from centroid
	for (auto &x : down) {
		update(x.second, +1);
	}
	for (auto &que : qu[cent]) {
		ans[que] += 1 + query(que);
	}
	for (auto &x : down) {
		update(x.second, -1);
	}

	for (auto &u : verts) {
		mark[u] = -1;
		tmp[u] = make_pair(-1, INT_MAX);
		has[u] = false;
	}
	verts.clear();
	used[cent] = true;
	for (auto &e : g[cent]) {
		int u = e.first;
		if (!used[u]) {
			decompose(u, sz[u]);
		}
	}
}

int qtype[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	memset(mark, -1, sizeof(mark));
	for (int i = 0; i < N; ++i) {
		tmp[i] = make_pair(-1, INT_MAX);
	}

	cin >> n >> k;
	for (int i = 0; i < n + k - 1; ++i) {
		char op;
		cin >> op;
		int v;
		cin >> v;
		--v;
		if (op == 'S') {
			int u;
			cin >> u;
			--u;
			g[v].push_back({u, i});
			g[u].push_back({v, i});
		} else if (op == 'Q') {
			qtype[i] = 1;
			int u;
			cin >> u;
			--u;
			qp[u].push_back({v, i});
		} else {
			qtype[i] = 2;
			qu[v].push_back(i);
		}
	}

	decompose(0, n);
	
	for (int i = 0; i < n + k - 1; ++i) {
		if (qtype[i] == 1) {
			cout << (ans[i] ? "yes" : "no") << '\n';
		} else if (qtype[i] == 2) {
			cout << ans[i] << '\n';
		}
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35780 KB Output is correct
2 Correct 50 ms 36236 KB Output is correct
3 Correct 46 ms 36012 KB Output is correct
4 Correct 53 ms 36372 KB Output is correct
5 Correct 57 ms 36104 KB Output is correct
6 Correct 47 ms 36040 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35780 KB Output is correct
2 Correct 50 ms 36236 KB Output is correct
3 Correct 46 ms 36012 KB Output is correct
4 Correct 53 ms 36372 KB Output is correct
5 Correct 57 ms 36104 KB Output is correct
6 Correct 47 ms 36040 KB Output is correct
7 Correct 41 ms 35832 KB Output is correct
8 Correct 57 ms 36880 KB Output is correct
9 Correct 54 ms 37180 KB Output is correct
10 Correct 58 ms 37020 KB Output is correct
11 Correct 52 ms 36780 KB Output is correct
12 Correct 46 ms 37200 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35812 KB Output is correct
2 Correct 155 ms 46500 KB Output is correct
3 Correct 169 ms 46412 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35812 KB Output is correct
2 Correct 155 ms 46500 KB Output is correct
3 Correct 169 ms 46412 KB Output is correct
4 Correct 39 ms 35860 KB Output is correct
5 Correct 148 ms 49012 KB Output is correct
6 Correct 106 ms 46544 KB Output is correct
7 Correct 114 ms 46612 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35736 KB Output is correct
2 Correct 354 ms 53184 KB Output is correct
3 Correct 312 ms 53152 KB Output is correct
4 Correct 293 ms 53476 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35736 KB Output is correct
2 Correct 354 ms 53184 KB Output is correct
3 Correct 312 ms 53152 KB Output is correct
4 Correct 293 ms 53476 KB Output is correct
5 Correct 40 ms 35800 KB Output is correct
6 Correct 324 ms 56356 KB Output is correct
7 Correct 317 ms 57372 KB Output is correct
8 Correct 317 ms 55608 KB Output is correct
9 Correct 324 ms 55516 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35708 KB Output is correct
2 Correct 294 ms 44976 KB Output is correct
3 Correct 292 ms 44240 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35708 KB Output is correct
2 Correct 294 ms 44976 KB Output is correct
3 Correct 292 ms 44240 KB Output is correct
4 Correct 37 ms 35780 KB Output is correct
5 Correct 359 ms 48832 KB Output is correct
6 Correct 287 ms 47128 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35780 KB Output is correct
2 Correct 326 ms 53072 KB Output is correct
3 Correct 332 ms 53260 KB Output is correct
4 Correct 307 ms 53384 KB Output is correct
5 Correct 38 ms 35780 KB Output is correct
6 Correct 302 ms 45048 KB Output is correct
7 Correct 342 ms 44060 KB Output is correct
8 Correct 271 ms 44668 KB Output is correct
9 Correct 312 ms 45388 KB Output is correct
10 Correct 386 ms 49208 KB Output is correct
11 Correct 372 ms 48136 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35780 KB Output is correct
2 Correct 326 ms 53072 KB Output is correct
3 Correct 332 ms 53260 KB Output is correct
4 Correct 307 ms 53384 KB Output is correct
5 Correct 38 ms 35780 KB Output is correct
6 Correct 302 ms 45048 KB Output is correct
7 Correct 342 ms 44060 KB Output is correct
8 Correct 271 ms 44668 KB Output is correct
9 Correct 312 ms 45388 KB Output is correct
10 Correct 386 ms 49208 KB Output is correct
11 Correct 372 ms 48136 KB Output is correct
12 Correct 39 ms 35784 KB Output is correct
13 Correct 352 ms 56584 KB Output is correct
14 Correct 301 ms 57372 KB Output is correct
15 Correct 340 ms 55688 KB Output is correct
16 Correct 307 ms 55612 KB Output is correct
17 Correct 39 ms 36568 KB Output is correct
18 Correct 344 ms 48872 KB Output is correct
19 Correct 297 ms 47220 KB Output is correct
20 Correct 299 ms 48380 KB Output is correct
21 Correct 315 ms 48736 KB Output is correct
22 Correct 365 ms 51616 KB Output is correct
23 Correct 513 ms 51524 KB Output is correct
24 Correct 531 ms 50796 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 35808 KB Output is correct
2 Correct 49 ms 36180 KB Output is correct
3 Correct 46 ms 36096 KB Output is correct
4 Correct 51 ms 36376 KB Output is correct
5 Correct 54 ms 36184 KB Output is correct
6 Correct 52 ms 36084 KB Output is correct
7 Correct 40 ms 35920 KB Output is correct
8 Correct 159 ms 46468 KB Output is correct
9 Correct 161 ms 46436 KB Output is correct
10 Correct 48 ms 35908 KB Output is correct
11 Correct 384 ms 53424 KB Output is correct
12 Correct 349 ms 53228 KB Output is correct
13 Correct 361 ms 53576 KB Output is correct
14 Correct 54 ms 35884 KB Output is correct
15 Correct 311 ms 45008 KB Output is correct
16 Correct 305 ms 44176 KB Output is correct
17 Correct 357 ms 44888 KB Output is correct
18 Correct 350 ms 45532 KB Output is correct
19 Correct 424 ms 49432 KB Output is correct
20 Correct 445 ms 48240 KB Output is correct
21 Correct 223 ms 45408 KB Output is correct
22 Correct 196 ms 45176 KB Output is correct
23 Correct 276 ms 45132 KB Output is correct
24 Correct 292 ms 45036 KB Output is correct
25 Correct 409 ms 51316 KB Output is correct
26 Correct 299 ms 42684 KB Output is correct
27 Correct 274 ms 42428 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 35808 KB Output is correct
2 Correct 49 ms 36180 KB Output is correct
3 Correct 46 ms 36096 KB Output is correct
4 Correct 51 ms 36376 KB Output is correct
5 Correct 54 ms 36184 KB Output is correct
6 Correct 52 ms 36084 KB Output is correct
7 Correct 40 ms 35920 KB Output is correct
8 Correct 159 ms 46468 KB Output is correct
9 Correct 161 ms 46436 KB Output is correct
10 Correct 48 ms 35908 KB Output is correct
11 Correct 384 ms 53424 KB Output is correct
12 Correct 349 ms 53228 KB Output is correct
13 Correct 361 ms 53576 KB Output is correct
14 Correct 54 ms 35884 KB Output is correct
15 Correct 311 ms 45008 KB Output is correct
16 Correct 305 ms 44176 KB Output is correct
17 Correct 357 ms 44888 KB Output is correct
18 Correct 350 ms 45532 KB Output is correct
19 Correct 424 ms 49432 KB Output is correct
20 Correct 445 ms 48240 KB Output is correct
21 Correct 223 ms 45408 KB Output is correct
22 Correct 196 ms 45176 KB Output is correct
23 Correct 276 ms 45132 KB Output is correct
24 Correct 292 ms 45036 KB Output is correct
25 Correct 409 ms 51316 KB Output is correct
26 Correct 299 ms 42684 KB Output is correct
27 Correct 274 ms 42428 KB Output is correct
28 Correct 42 ms 36048 KB Output is correct
29 Correct 54 ms 36896 KB Output is correct
30 Correct 48 ms 37196 KB Output is correct
31 Correct 57 ms 37016 KB Output is correct
32 Correct 55 ms 36664 KB Output is correct
33 Correct 48 ms 37228 KB Output is correct
34 Correct 46 ms 36608 KB Output is correct
35 Correct 156 ms 49036 KB Output is correct
36 Correct 118 ms 46392 KB Output is correct
37 Correct 118 ms 46748 KB Output is correct
38 Correct 40 ms 36684 KB Output is correct
39 Correct 366 ms 56476 KB Output is correct
40 Correct 319 ms 57348 KB Output is correct
41 Correct 311 ms 55636 KB Output is correct
42 Correct 333 ms 55696 KB Output is correct
43 Correct 39 ms 36520 KB Output is correct
44 Correct 311 ms 48844 KB Output is correct
45 Correct 295 ms 47228 KB Output is correct
46 Correct 296 ms 48300 KB Output is correct
47 Correct 307 ms 48736 KB Output is correct
48 Correct 375 ms 51532 KB Output is correct
49 Correct 563 ms 51592 KB Output is correct
50 Correct 493 ms 50796 KB Output is correct
51 Correct 144 ms 47604 KB Output is correct
52 Correct 121 ms 48288 KB Output is correct
53 Correct 115 ms 47024 KB Output is correct
54 Correct 130 ms 47564 KB Output is correct
55 Correct 173 ms 45972 KB Output is correct
56 Correct 215 ms 47460 KB Output is correct
57 Correct 313 ms 53288 KB Output is correct
58 Correct 333 ms 46996 KB Output is correct
59 Correct 273 ms 45876 KB Output is correct