oj.uz

Submission #551491

# Submission time Handle Problem Language Result Execution time Memory
551491 2022-04-20T21:13:53 Z sidon Inside information (BOI21_servers) C++17
50 / 100
 285 ms 33248 KB 
#include <bits/stdc++.h>
using namespace std;

const int Z = 1.2e5, B = 17;

int N, K, p[Z][B], up[Z][2], d[Z], pE[Z], res[Z];
vector<array<int, 2>> g[Z], h[Z];
vector<array<int, 4>> pQ;

void init(const int &u) {
	for(int i = 0; i + 1 < B; ++i)
		p[u][i+1] = p[p[u][i]][i];

	for(const auto &[v, i] : g[u]) if(v != p[u][0]) {
		p[v][0] = u;
		d[v] = d[u] + 1;
		pE[v] = i;

		if(pE[u] < i) {
			up[v][0] = up[u][0];
			up[v][1] = u;
		} else {
			up[v][0] = u;
			up[v][1] = up[u][1];
		}

		init(v);
	}
}

int _u, _v;

int lca(int u, int v) {
	bool swapped = 0;
	if((swapped = (d[u] < d[v]))) swap(u, v);

	if(d[u] > d[v]) {
		for(int i = B; i--; ) if((d[u] - d[v] - 1) & (1<<i))
			u = p[u][i];

		if(p[u][0] == v) {
			_u = u;
			return v;
		}
		u = p[u][0];
	}

	for(int i = B; i--; ) if(p[u][i] != p[v][i])
		u = p[u][i], v = p[v][i];
	if(swapped) swap(u, v);
	_u = u, _v = v;
	return p[u][0];
}

int main() {
	cin >> N >> K;

	for(int i {}, j {}; i < N - 1 + K; ++i) {
		char t; int u, v;
		cin >> t >> u; --u;
		if(t == 'S') {
			cin >> v; --v;
			g[u].push_back({v, i});
			g[v].push_back({u, i});
		}
		if(t == 'Q') {
			cin >> v; --v;
			pQ.push_back({j++, i, u, v});
		}

		if(t == 'C')
			h[u].push_back({j++, i});
	}

	init(0);

	for(const auto &[j, i, u, v] : pQ) {
		int w = lca(u, v), val = w == u ? pE[_u] : pE[u];

		if(w != u && w != v && pE[_u] < pE[_v])
			val = i;

		if(u == v || (max(d[up[u][0]], d[up[v][1]]) <= d[w] && val < i))
			res[j] = -1;
		else
			res[j] = -2;
	}

	for(int j = 0; j < K; ++j) {
		if(res[j] < 0) cout << (res[j] & 1 ? "yes" : "no");
		else assert(0);
		cout << '\n';
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 69 ms 9716 KB Output is correct
2 Correct 96 ms 10588 KB Output is correct
3 Correct 86 ms 10564 KB Output is correct
4 Correct 98 ms 10556 KB Output is correct
5 Correct 90 ms 10868 KB Output is correct
6 Correct 86 ms 10528 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 69 ms 9716 KB Output is correct
2 Correct 96 ms 10588 KB Output is correct
3 Correct 86 ms 10564 KB Output is correct
4 Correct 98 ms 10556 KB Output is correct
5 Correct 90 ms 10868 KB Output is correct
6 Correct 86 ms 10528 KB Output is correct
7 Runtime error 65 ms 17568 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 9680 KB Output is correct
2 Correct 203 ms 26164 KB Output is correct
3 Correct 198 ms 26088 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 9680 KB Output is correct
2 Correct 203 ms 26164 KB Output is correct
3 Correct 198 ms 26088 KB Output is correct
4 Runtime error 64 ms 17508 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 9640 KB Output is correct
2 Correct 234 ms 33236 KB Output is correct
3 Correct 221 ms 33248 KB Output is correct
4 Correct 210 ms 33056 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 9640 KB Output is correct
2 Correct 234 ms 33236 KB Output is correct
3 Correct 221 ms 33248 KB Output is correct
4 Correct 210 ms 33056 KB Output is correct
5 Runtime error 61 ms 17544 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9628 KB Output is correct
2 Correct 211 ms 26484 KB Output is correct
3 Correct 215 ms 26916 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9628 KB Output is correct
2 Correct 211 ms 26484 KB Output is correct
3 Correct 215 ms 26916 KB Output is correct
4 Runtime error 67 ms 17592 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 9576 KB Output is correct
2 Correct 236 ms 33136 KB Output is correct
3 Correct 228 ms 33060 KB Output is correct
4 Correct 215 ms 33040 KB Output is correct
5 Correct 65 ms 9644 KB Output is correct
6 Correct 205 ms 26400 KB Output is correct
7 Correct 223 ms 27068 KB Output is correct
8 Correct 242 ms 27368 KB Output is correct
9 Correct 234 ms 27304 KB Output is correct
10 Correct 253 ms 31196 KB Output is correct
11 Correct 285 ms 30580 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 9576 KB Output is correct
2 Correct 236 ms 33136 KB Output is correct
3 Correct 228 ms 33060 KB Output is correct
4 Correct 215 ms 33040 KB Output is correct
5 Correct 65 ms 9644 KB Output is correct
6 Correct 205 ms 26400 KB Output is correct
7 Correct 223 ms 27068 KB Output is correct
8 Correct 242 ms 27368 KB Output is correct
9 Correct 234 ms 27304 KB Output is correct
10 Correct 253 ms 31196 KB Output is correct
11 Correct 285 ms 30580 KB Output is correct
12 Runtime error 63 ms 17620 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 70 ms 9648 KB Output is correct
2 Correct 92 ms 10468 KB Output is correct
3 Correct 85 ms 10600 KB Output is correct
4 Correct 95 ms 10512 KB Output is correct
5 Correct 92 ms 10816 KB Output is correct
6 Correct 89 ms 10584 KB Output is correct
7 Correct 65 ms 9672 KB Output is correct
8 Correct 226 ms 26004 KB Output is correct
9 Correct 218 ms 26028 KB Output is correct
10 Correct 63 ms 9640 KB Output is correct
11 Correct 229 ms 33080 KB Output is correct
12 Correct 225 ms 33220 KB Output is correct
13 Correct 208 ms 33064 KB Output is correct
14 Correct 66 ms 9656 KB Output is correct
15 Correct 213 ms 26472 KB Output is correct
16 Correct 223 ms 26992 KB Output is correct
17 Correct 250 ms 27324 KB Output is correct
18 Correct 234 ms 27296 KB Output is correct
19 Correct 246 ms 31188 KB Output is correct
20 Correct 272 ms 30592 KB Output is correct
21 Correct 233 ms 26588 KB Output is correct
22 Correct 210 ms 26664 KB Output is correct
23 Correct 222 ms 26860 KB Output is correct
24 Correct 226 ms 26916 KB Output is correct
25 Correct 235 ms 28316 KB Output is correct
26 Correct 228 ms 26472 KB Output is correct
27 Correct 222 ms 26480 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 70 ms 9648 KB Output is correct
2 Correct 92 ms 10468 KB Output is correct
3 Correct 85 ms 10600 KB Output is correct
4 Correct 95 ms 10512 KB Output is correct
5 Correct 92 ms 10816 KB Output is correct
6 Correct 89 ms 10584 KB Output is correct
7 Correct 65 ms 9672 KB Output is correct
8 Correct 226 ms 26004 KB Output is correct
9 Correct 218 ms 26028 KB Output is correct
10 Correct 63 ms 9640 KB Output is correct
11 Correct 229 ms 33080 KB Output is correct
12 Correct 225 ms 33220 KB Output is correct
13 Correct 208 ms 33064 KB Output is correct
14 Correct 66 ms 9656 KB Output is correct
15 Correct 213 ms 26472 KB Output is correct
16 Correct 223 ms 26992 KB Output is correct
17 Correct 250 ms 27324 KB Output is correct
18 Correct 234 ms 27296 KB Output is correct
19 Correct 246 ms 31188 KB Output is correct
20 Correct 272 ms 30592 KB Output is correct
21 Correct 233 ms 26588 KB Output is correct
22 Correct 210 ms 26664 KB Output is correct
23 Correct 222 ms 26860 KB Output is correct
24 Correct 226 ms 26916 KB Output is correct
25 Correct 235 ms 28316 KB Output is correct
26 Correct 228 ms 26472 KB Output is correct
27 Correct 222 ms 26480 KB Output is correct
28 Runtime error 65 ms 17596 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -