oj.uz

Submission #511310

# Submission time Handle Problem Language Result Execution time Memory
511310 2022-01-15T14:11:30 Z Elegia Inside information (BOI21_servers) C++17
100 / 100
 481 ms 33416 KB 
#include <cmath>

#include <algorithm>
#include <stack>
#include <bitset>
#include <numeric>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>

using ull = unsigned long long;

using std::vector;
using std::pair;
using std::function;
using std::ios;
using std::cin;
using std::cout;

const int _ = 120007;

int N;
char opt[_];
int x[_], y[_], t[_], ans[_], siz[_], sprt[_], pw[_];
bool vis[_], inc[_], dec[_];
vector<pair<int, int>> G[_];
vector<int> sub[_];

int fw[_];
void ch(int k, int x) { for (; k <= N; k += k & -k) fw[k] += x; }
int qry(int k) { int ret = 0; for (; k; k &= k - 1) ret += fw[k]; return ret; }

void solve(int rt, const vector<int>& query) {
	function<void(int, int)> dfs = [&](int u, int p) {
		siz[u] = 1;
		for (auto [v, w] : G[u]) if (!vis[v] && v != p) {
			dfs(v, u); siz[u] += siz[v];
		}
	};
	dfs(rt, 0);
	function<int(int)> cent = [&](int u) {
		for (auto [v, w] : G[u]) if (!vis[v] && siz[v] < siz[u] && siz[v] * 2 >= siz[rt])
			return cent(v);
		return u;
	};
	vis[rt = cent(rt)] = true;
	inc[rt] = dec[rt] = true; sprt[rt] = pw[rt] = 0;
	vector<pair<int, int>> pt;
	function<void(int, int)> dfs2 = [&](int u, int p) {
		if (dec[u]) pt.emplace_back(pw[sprt[u]], -pw[u]);
		for (auto [v, w] : G[u]) if (!vis[v] && v != p) {
			sprt[v] = sprt[u]; pw[v] = w;
			inc[v] = inc[u] && w < pw[u];
			dec[v] = dec[u] && w > pw[u];
			dfs2(v, u);
		}
	};
	for (auto [v, w] : G[rt]) if (!vis[v]) {
		sprt[v] = v; pw[v] = w; inc[v] = dec[v] = true;
		dfs2(v, rt);
	}
	for (int i : query)
		if (opt[i] == 'Q') {
			if (x[i] == y[i]) continue;
			if (sprt[x[i]] && sprt[y[i]] && sprt[x[i]] == sprt[y[i]]) {
				sub[sprt[x[i]]].push_back(i);
				continue;
			}
			if (!inc[x[i]] || !dec[y[i]]) { ans[i] = 0; continue; }
			if (sprt[x[i]] && sprt[y[i]] && pw[sprt[x[i]]] > pw[sprt[y[i]]]) ans[i] = 0;
			int lst = pw[y[i]]; if (!lst) lst = pw[sprt[x[i]]];
			ans[i] &= lst <= t[i];
		} else {
			if (!inc[x[i]]) {
				if (x[i] != rt) sub[sprt[x[i]]].push_back(i);
				continue;
			}
			if (x[i] != rt) {
				int sp = sprt[x[i]];
				pt.emplace_back(pw[sp], i);
				ans[i] += pw[sp] <= t[i];
				sub[sp].push_back(i);
			} else {
				pt.emplace_back(0, i);
				++ans[i];
			}
		}
	sort(pt.begin(), pt.end(), std::greater<pair<int, int>>());
	for (auto [i, j] : pt) {
		if (j < 0) ch(-j, 1);
		else ans[j] += qry(t[j]);
	}
	for (auto [i, j] : pt) if (j < 0) ch(-j, -1);
	for (auto [v, w] : G[rt]) if (!vis[v]) {
		vector<int> tmp; swap(tmp, sub[v]);
		solve(v, tmp);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	int K; cin >> N >> K;
	int clo = 0, cnt = 0;
	for (int rep = 0; rep != N + K - 1; ++rep) {
		char o; int u, v; cin >> o >> u;
		if (o == 'S') {
			cin >> v; ++clo;
			G[u].emplace_back(v, clo);
			G[v].emplace_back(u, clo);
		} else {
			++cnt;
			if (o == 'Q') { cin >> v; std::swap(u, v); ans[cnt] = 1; }
			opt[cnt] = o; x[cnt] = u; y[cnt] = v; t[cnt] = clo;
		}
	}
	vector<int> all(K); iota(all.begin(), all.end(), 1);
	solve(1, all);
	for (int i = 1; i <= K; ++i)
		if (opt[i] == 'Q') cout << (ans[i] ? "yes\n" : "no\n");
		else cout << ans[i] << '\n';

	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 9756 KB Output is correct
2 Correct 34 ms 10492 KB Output is correct
3 Correct 39 ms 10796 KB Output is correct
4 Correct 34 ms 10784 KB Output is correct
5 Correct 39 ms 11092 KB Output is correct
6 Correct 32 ms 10496 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 9756 KB Output is correct
2 Correct 34 ms 10492 KB Output is correct
3 Correct 39 ms 10796 KB Output is correct
4 Correct 34 ms 10784 KB Output is correct
5 Correct 39 ms 11092 KB Output is correct
6 Correct 32 ms 10496 KB Output is correct
7 Correct 25 ms 9868 KB Output is correct
8 Correct 46 ms 10312 KB Output is correct
9 Correct 61 ms 10868 KB Output is correct
10 Correct 55 ms 10676 KB Output is correct
11 Correct 48 ms 10828 KB Output is correct
12 Correct 37 ms 10672 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 9668 KB Output is correct
2 Correct 85 ms 19192 KB Output is correct
3 Correct 87 ms 19260 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 9668 KB Output is correct
2 Correct 85 ms 19192 KB Output is correct
3 Correct 87 ms 19260 KB Output is correct
4 Correct 24 ms 9804 KB Output is correct
5 Correct 118 ms 19636 KB Output is correct
6 Correct 105 ms 18944 KB Output is correct
7 Correct 97 ms 20344 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 9828 KB Output is correct
2 Correct 297 ms 31720 KB Output is correct
3 Correct 323 ms 31680 KB Output is correct
4 Correct 177 ms 32532 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 9828 KB Output is correct
2 Correct 297 ms 31720 KB Output is correct
3 Correct 323 ms 31680 KB Output is correct
4 Correct 177 ms 32532 KB Output is correct
5 Correct 34 ms 9816 KB Output is correct
6 Correct 323 ms 31332 KB Output is correct
7 Correct 256 ms 33416 KB Output is correct
8 Correct 333 ms 31092 KB Output is correct
9 Correct 324 ms 31036 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 9820 KB Output is correct
2 Correct 195 ms 20184 KB Output is correct
3 Correct 210 ms 19716 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 9820 KB Output is correct
2 Correct 195 ms 20184 KB Output is correct
3 Correct 210 ms 19716 KB Output is correct
4 Correct 24 ms 9896 KB Output is correct
5 Correct 245 ms 20264 KB Output is correct
6 Correct 261 ms 19372 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9824 KB Output is correct
2 Correct 342 ms 31692 KB Output is correct
3 Correct 334 ms 31764 KB Output is correct
4 Correct 198 ms 32456 KB Output is correct
5 Correct 28 ms 9828 KB Output is correct
6 Correct 178 ms 20212 KB Output is correct
7 Correct 261 ms 19740 KB Output is correct
8 Correct 291 ms 20036 KB Output is correct
9 Correct 297 ms 20164 KB Output is correct
10 Correct 357 ms 26424 KB Output is correct
11 Correct 320 ms 25136 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9824 KB Output is correct
2 Correct 342 ms 31692 KB Output is correct
3 Correct 334 ms 31764 KB Output is correct
4 Correct 198 ms 32456 KB Output is correct
5 Correct 28 ms 9828 KB Output is correct
6 Correct 178 ms 20212 KB Output is correct
7 Correct 261 ms 19740 KB Output is correct
8 Correct 291 ms 20036 KB Output is correct
9 Correct 297 ms 20164 KB Output is correct
10 Correct 357 ms 26424 KB Output is correct
11 Correct 320 ms 25136 KB Output is correct
12 Correct 24 ms 9852 KB Output is correct
13 Correct 344 ms 31312 KB Output is correct
14 Correct 281 ms 33348 KB Output is correct
15 Correct 335 ms 31060 KB Output is correct
16 Correct 352 ms 31088 KB Output is correct
17 Correct 27 ms 10004 KB Output is correct
18 Correct 321 ms 20296 KB Output is correct
19 Correct 277 ms 19348 KB Output is correct
20 Correct 322 ms 19872 KB Output is correct
21 Correct 338 ms 20096 KB Output is correct
22 Correct 481 ms 25828 KB Output is correct
23 Correct 454 ms 25496 KB Output is correct
24 Correct 451 ms 25320 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9716 KB Output is correct
2 Correct 41 ms 10504 KB Output is correct
3 Correct 34 ms 10840 KB Output is correct
4 Correct 38 ms 10776 KB Output is correct
5 Correct 40 ms 11024 KB Output is correct
6 Correct 45 ms 10536 KB Output is correct
7 Correct 24 ms 9672 KB Output is correct
8 Correct 126 ms 19200 KB Output is correct
9 Correct 87 ms 19144 KB Output is correct
10 Correct 26 ms 9828 KB Output is correct
11 Correct 270 ms 31788 KB Output is correct
12 Correct 300 ms 31652 KB Output is correct
13 Correct 179 ms 32484 KB Output is correct
14 Correct 27 ms 9820 KB Output is correct
15 Correct 191 ms 20196 KB Output is correct
16 Correct 222 ms 19732 KB Output is correct
17 Correct 231 ms 20152 KB Output is correct
18 Correct 237 ms 20064 KB Output is correct
19 Correct 332 ms 26476 KB Output is correct
20 Correct 262 ms 25200 KB Output is correct
21 Correct 112 ms 20576 KB Output is correct
22 Correct 104 ms 20408 KB Output is correct
23 Correct 196 ms 19848 KB Output is correct
24 Correct 173 ms 20056 KB Output is correct
25 Correct 298 ms 26884 KB Output is correct
26 Correct 263 ms 19120 KB Output is correct
27 Correct 240 ms 19260 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9716 KB Output is correct
2 Correct 41 ms 10504 KB Output is correct
3 Correct 34 ms 10840 KB Output is correct
4 Correct 38 ms 10776 KB Output is correct
5 Correct 40 ms 11024 KB Output is correct
6 Correct 45 ms 10536 KB Output is correct
7 Correct 24 ms 9672 KB Output is correct
8 Correct 126 ms 19200 KB Output is correct
9 Correct 87 ms 19144 KB Output is correct
10 Correct 26 ms 9828 KB Output is correct
11 Correct 270 ms 31788 KB Output is correct
12 Correct 300 ms 31652 KB Output is correct
13 Correct 179 ms 32484 KB Output is correct
14 Correct 27 ms 9820 KB Output is correct
15 Correct 191 ms 20196 KB Output is correct
16 Correct 222 ms 19732 KB Output is correct
17 Correct 231 ms 20152 KB Output is correct
18 Correct 237 ms 20064 KB Output is correct
19 Correct 332 ms 26476 KB Output is correct
20 Correct 262 ms 25200 KB Output is correct
21 Correct 112 ms 20576 KB Output is correct
22 Correct 104 ms 20408 KB Output is correct
23 Correct 196 ms 19848 KB Output is correct
24 Correct 173 ms 20056 KB Output is correct
25 Correct 298 ms 26884 KB Output is correct
26 Correct 263 ms 19120 KB Output is correct
27 Correct 240 ms 19260 KB Output is correct
28 Correct 33 ms 9820 KB Output is correct
29 Correct 56 ms 10280 KB Output is correct
30 Correct 47 ms 10956 KB Output is correct
31 Correct 52 ms 10664 KB Output is correct
32 Correct 54 ms 10928 KB Output is correct
33 Correct 39 ms 10700 KB Output is correct
34 Correct 29 ms 9804 KB Output is correct
35 Correct 87 ms 19648 KB Output is correct
36 Correct 95 ms 18916 KB Output is correct
37 Correct 128 ms 20280 KB Output is correct
38 Correct 33 ms 9756 KB Output is correct
39 Correct 306 ms 31420 KB Output is correct
40 Correct 289 ms 33368 KB Output is correct
41 Correct 311 ms 31068 KB Output is correct
42 Correct 319 ms 31084 KB Output is correct
43 Correct 35 ms 9956 KB Output is correct
44 Correct 255 ms 20308 KB Output is correct
45 Correct 252 ms 19536 KB Output is correct
46 Correct 329 ms 19932 KB Output is correct
47 Correct 285 ms 20028 KB Output is correct
48 Correct 441 ms 25708 KB Output is correct
49 Correct 444 ms 25632 KB Output is correct
50 Correct 380 ms 25304 KB Output is correct
51 Correct 124 ms 22164 KB Output is correct
52 Correct 119 ms 21096 KB Output is correct
53 Correct 118 ms 20788 KB Output is correct
54 Correct 140 ms 20108 KB Output is correct
55 Correct 137 ms 23324 KB Output is correct
56 Correct 222 ms 20636 KB Output is correct
57 Correct 296 ms 31868 KB Output is correct
58 Correct 359 ms 19544 KB Output is correct
59 Correct 255 ms 19248 KB Output is correct