oj.uz

Submission #591161

# Submission time Handle Problem Language Result Execution time Memory
591161 2022-07-06T23:45:25 Z GusterGoose27 Inside information (BOI21_servers) C++11
55 / 100
 257 ms 78024 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 120000;
vector<pii> edges[MAXN];
pair<pii, int> queries[MAXN]; // start, end, time
int lca[MAXN][20];
pii lca_range[MAXN][20];
pii lca_range_rev[MAXN][20];
int rev_lca[MAXN][20];
bool flag = 0;
int depth[MAXN];
int n, k;

void dfs(int cur = 0, int p = -1) {
	for (pii e: edges[cur]) {
		int next = e.first;
		if (next == p) continue;
		depth[next] = depth[cur]+1;
		lca[next][0] = cur;
		lca_range[next][0] = pii(e.second, e.second);
		lca_range_rev[next][0] = pii(e.second, e.second);
		if (flag) {
			rev_lca[cur][0] = next;
		}
		dfs(next, cur);
	}
}

bool move(int &i, int pow, int &s) {
	pii r = lca_range[i][pow];
	if (s >= r.first) return 0;
	s = r.second;
	i = lca[i][pow];
	return 1;
}

void move_u(int &i, int pow, int &s, int t) {
	pii r = lca_range[i][pow];
	if (s >= r.first || r.second >= t) return;
	s = r.second;
	i = lca[i][pow];
}

void move_d(int &i, int pow, int &s, int t) {
	int next = rev_lca[i][pow];
	pii r = lca_range_rev[next][pow];
	if (s >= r.first || r.second >= t) return;
	s = r.second;
	i = next;
}

bool move_rev(int &i, int pow, int &e) {
	pii r = lca_range_rev[i][pow];
	if (r.second >= e || r.second == -1) return 0;
	e = r.first;
	i = lca[i][pow];
	return 1;
}

bool calc_lca(int a, int b, int e) {
	int s = -1;
	int diff = depth[a]-depth[b];
	int pow = 0;
	while (diff > 0) {
		if (diff & 1) {
			bool bo = move(a, pow, s);
			if (!bo) {
				return 0;
			}
		}
		pow++;
		diff /= 2;
	}
	diff = depth[b]-depth[a];
	pow = 0;
	while (diff > 0) {
		if (diff & 1) {
			bool bo = move_rev(b, pow, e);
			if (!bo) {
				return 0;
			}
		}
		pow++;
		diff /= 2;
	}
	for (int i = 19; i >= 0; i--) {
		if (lca[a][i] != lca[b][i]) {
			bool bo = move(a, i, s);
			if (!bo) {
				return 0;
			}
			bo = move_rev(b, i, e);
			if (!bo) {
				return 0;
			}
		}
	}
	if (a != b) {
		bool bo = move(a, 0, s);
		if (!bo) {
			return 0;
		}
		bo = move_rev(b, 0, e);
		if (!bo) {
			return 0;
		}
	}
	if (s >= e) {
		return 0;
	}
	return 1;
}

int spec(int i) {
	int q = queries[i].first.first;
	int t = queries[i].first.second;
	int u = q;
	int d = q;
	int s1 = -1;
	int s2 = -1;
	for (int i = 19; i >= 0; i--) {
		move_u(u, i, s1, t);
		move_d(d, i, s2, t);
	}
	return (depth[d]-depth[u]+1);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> k;
	int t = 0;
	int p = 0;
	for (int i = 0; i < n+k-1; i++) {
		char c;
		int a, b;
		cin >> c >> a;
		a--;
		if (c == 'C') {
			queries[p++] = pair<pii, int>(pii(a, t), -1);
			flag = 1;
			continue;
		}
		cin >> b; b--;
		if (c == 'S') {
			edges[a].push_back(pii(b, t));
			edges[b].push_back(pii(a, t));
			t++;
		}
		else {
			queries[p] = pair<pii, int>(pii(b, a), t);
			p++;
		}
	}
	assert(t == n-1);
	assert(p == k);
	dfs();
	lca_range[0][0] = pii(-1, -1);
	lca_range_rev[0][0] = pii(-1, -1);
	if (flag) rev_lca[n-1][0] = n-1;
	for (int i = 1; i < 20; i++) {
		for (int j = 0; j < n; j++) {
			lca[j][i] = lca[lca[j][i-1]][i-1];
			pii r1 = lca_range[j][i-1];
			pii r2 = lca_range[lca[j][i-1]][i-1];
			if (r1.second >= 0 && r1.second < r2.first) lca_range[j][i] = pii(r1.first, r2.second);
			else lca_range[j][i] = pii(-1, -1);
			r1 = lca_range_rev[j][i-1];
			r2 = lca_range_rev[lca[j][i-1]][i-1];
			if (r2.second >= 0 && r2.second < r1.first) lca_range_rev[j][i] = pii(r2.first, r1.second);
			else lca_range_rev[j][i] = pii(-1, -1);
			if (flag) rev_lca[j][i] = rev_lca[rev_lca[j][i-1]][i-1];
		}
	}
	for (int i = 0; i < k; i++) {
		if (queries[i].second == -1) {
			cout << spec(i) << "\n";
			continue;
		}
		bool b = calc_lca(queries[i].first.first, queries[i].first.second, queries[i].second);
		if (b) cout << "yes\n";
		else cout << "no\n";
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4916 KB Output is correct
2 Correct 30 ms 6576 KB Output is correct
3 Correct 30 ms 6660 KB Output is correct
4 Correct 38 ms 6688 KB Output is correct
5 Correct 31 ms 6952 KB Output is correct
6 Correct 34 ms 6724 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4916 KB Output is correct
2 Correct 30 ms 6576 KB Output is correct
3 Correct 30 ms 6660 KB Output is correct
4 Correct 38 ms 6688 KB Output is correct
5 Correct 31 ms 6952 KB Output is correct
6 Correct 34 ms 6724 KB Output is correct
7 Incorrect 25 ms 5024 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4976 KB Output is correct
2 Correct 175 ms 57024 KB Output is correct
3 Correct 161 ms 57264 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4976 KB Output is correct
2 Correct 175 ms 57024 KB Output is correct
3 Correct 161 ms 57264 KB Output is correct
4 Incorrect 24 ms 5076 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4948 KB Output is correct
2 Correct 176 ms 65584 KB Output is correct
3 Correct 182 ms 65564 KB Output is correct
4 Correct 173 ms 65628 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4948 KB Output is correct
2 Correct 176 ms 65584 KB Output is correct
3 Correct 182 ms 65564 KB Output is correct
4 Correct 173 ms 65628 KB Output is correct
5 Correct 28 ms 5012 KB Output is correct
6 Correct 205 ms 74892 KB Output is correct
7 Correct 218 ms 78024 KB Output is correct
8 Correct 212 ms 77352 KB Output is correct
9 Correct 232 ms 77392 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4940 KB Output is correct
2 Correct 169 ms 57124 KB Output is correct
3 Correct 172 ms 57476 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4940 KB Output is correct
2 Correct 169 ms 57124 KB Output is correct
3 Correct 172 ms 57476 KB Output is correct
4 Incorrect 24 ms 4988 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4852 KB Output is correct
2 Correct 204 ms 65548 KB Output is correct
3 Correct 170 ms 65516 KB Output is correct
4 Correct 180 ms 65504 KB Output is correct
5 Correct 23 ms 4972 KB Output is correct
6 Correct 161 ms 57060 KB Output is correct
7 Correct 170 ms 57524 KB Output is correct
8 Correct 179 ms 57932 KB Output is correct
9 Correct 207 ms 57944 KB Output is correct
10 Correct 203 ms 62416 KB Output is correct
11 Correct 219 ms 61728 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4852 KB Output is correct
2 Correct 204 ms 65548 KB Output is correct
3 Correct 170 ms 65516 KB Output is correct
4 Correct 180 ms 65504 KB Output is correct
5 Correct 23 ms 4972 KB Output is correct
6 Correct 161 ms 57060 KB Output is correct
7 Correct 170 ms 57524 KB Output is correct
8 Correct 179 ms 57932 KB Output is correct
9 Correct 207 ms 57944 KB Output is correct
10 Correct 203 ms 62416 KB Output is correct
11 Correct 219 ms 61728 KB Output is correct
12 Correct 21 ms 5044 KB Output is correct
13 Correct 223 ms 74944 KB Output is correct
14 Correct 236 ms 77900 KB Output is correct
15 Correct 235 ms 77388 KB Output is correct
16 Correct 234 ms 77416 KB Output is correct
17 Incorrect 23 ms 5796 KB Extra information in the output file
18 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4948 KB Output is correct
2 Correct 29 ms 6612 KB Output is correct
3 Correct 32 ms 6712 KB Output is correct
4 Correct 28 ms 6696 KB Output is correct
5 Correct 30 ms 6904 KB Output is correct
6 Correct 31 ms 6684 KB Output is correct
7 Correct 22 ms 4924 KB Output is correct
8 Correct 164 ms 57072 KB Output is correct
9 Correct 168 ms 57136 KB Output is correct
10 Correct 20 ms 4948 KB Output is correct
11 Correct 171 ms 65456 KB Output is correct
12 Correct 184 ms 65504 KB Output is correct
13 Correct 178 ms 65616 KB Output is correct
14 Correct 22 ms 4900 KB Output is correct
15 Correct 170 ms 57052 KB Output is correct
16 Correct 168 ms 57500 KB Output is correct
17 Correct 186 ms 57936 KB Output is correct
18 Correct 193 ms 58004 KB Output is correct
19 Correct 203 ms 62372 KB Output is correct
20 Correct 257 ms 61760 KB Output is correct
21 Correct 162 ms 57084 KB Output is correct
22 Correct 181 ms 57004 KB Output is correct
23 Correct 186 ms 57548 KB Output is correct
24 Correct 173 ms 57548 KB Output is correct
25 Correct 223 ms 59304 KB Output is correct
26 Correct 195 ms 56908 KB Output is correct
27 Correct 178 ms 56884 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4948 KB Output is correct
2 Correct 29 ms 6612 KB Output is correct
3 Correct 32 ms 6712 KB Output is correct
4 Correct 28 ms 6696 KB Output is correct
5 Correct 30 ms 6904 KB Output is correct
6 Correct 31 ms 6684 KB Output is correct
7 Correct 22 ms 4924 KB Output is correct
8 Correct 164 ms 57072 KB Output is correct
9 Correct 168 ms 57136 KB Output is correct
10 Correct 20 ms 4948 KB Output is correct
11 Correct 171 ms 65456 KB Output is correct
12 Correct 184 ms 65504 KB Output is correct
13 Correct 178 ms 65616 KB Output is correct
14 Correct 22 ms 4900 KB Output is correct
15 Correct 170 ms 57052 KB Output is correct
16 Correct 168 ms 57500 KB Output is correct
17 Correct 186 ms 57936 KB Output is correct
18 Correct 193 ms 58004 KB Output is correct
19 Correct 203 ms 62372 KB Output is correct
20 Correct 257 ms 61760 KB Output is correct
21 Correct 162 ms 57084 KB Output is correct
22 Correct 181 ms 57004 KB Output is correct
23 Correct 186 ms 57548 KB Output is correct
24 Correct 173 ms 57548 KB Output is correct
25 Correct 223 ms 59304 KB Output is correct
26 Correct 195 ms 56908 KB Output is correct
27 Correct 178 ms 56884 KB Output is correct
28 Incorrect 34 ms 5072 KB Extra information in the output file
29 Halted 0 ms 0 KB -