oj.uz

Submission #591166

# Submission time Handle Problem Language Result Execution time Memory
591166 2022-07-06T23:52:53 Z GusterGoose27 Inside information (BOI21_servers) C++11
55 / 100
 3500 ms 75096 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;
bool flag2 = 0;
int depth[MAXN];
int n, k;
vector<int> ac_times[4000];

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) {
	if (flag) {
		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);
	}
	// n <= 4000
	int q = queries[i].first.first;
	int t = queries[i].first.second;
	int mn = -1;
	int mx = n;
	while (mx > mn+1) {
		int cur = (mn+mx)/2;
		if (ac_times[q][cur] > t) mx = cur;
		else mn = cur;
	}
	return mx;
}

void make_spec() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int mn = -1;
			int mx = n;
			while (mx > mn+1) {
				int cur = (mn+mx)/2;
				if (calc_lca(i, j, cur)) mx = cur;
				else mn = cur;
			}
			ac_times[i].push_back(mx);
		}
		sort(ac_times[i].begin(), ac_times[i].end());
	}
}

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);
			if (n > 4000) flag = 1;
			flag2 = 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];
		}
	}
	if (flag2 && !flag) make_spec();
	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 23 ms 4940 KB Output is correct
2 Correct 40 ms 6836 KB Output is correct
3 Correct 32 ms 6896 KB Output is correct
4 Correct 29 ms 6984 KB Output is correct
5 Correct 31 ms 7184 KB Output is correct
6 Correct 29 ms 6904 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4940 KB Output is correct
2 Correct 40 ms 6836 KB Output is correct
3 Correct 32 ms 6896 KB Output is correct
4 Correct 29 ms 6984 KB Output is correct
5 Correct 31 ms 7184 KB Output is correct
6 Correct 29 ms 6904 KB Output is correct
7 Correct 25 ms 4968 KB Output is correct
8 Correct 3476 ms 71140 KB Output is correct
9 Execution timed out 3546 ms 63348 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5076 KB Output is correct
2 Correct 168 ms 57296 KB Output is correct
3 Correct 156 ms 57308 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5076 KB Output is correct
2 Correct 168 ms 57296 KB Output is correct
3 Correct 156 ms 57308 KB Output is correct
4 Correct 23 ms 5076 KB Output is correct
5 Incorrect 203 ms 66708 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4948 KB Output is correct
2 Correct 169 ms 65704 KB Output is correct
3 Correct 186 ms 65748 KB Output is correct
4 Correct 172 ms 65700 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4948 KB Output is correct
2 Correct 169 ms 65704 KB Output is correct
3 Correct 186 ms 65748 KB Output is correct
4 Correct 172 ms 65700 KB Output is correct
5 Correct 22 ms 5060 KB Output is correct
6 Correct 215 ms 74940 KB Output is correct
7 Correct 249 ms 75084 KB Output is correct
8 Correct 214 ms 75048 KB Output is correct
9 Correct 227 ms 74920 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4948 KB Output is correct
2 Correct 157 ms 57244 KB Output is correct
3 Correct 167 ms 57752 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4948 KB Output is correct
2 Correct 157 ms 57244 KB Output is correct
3 Correct 167 ms 57752 KB Output is correct
4 Correct 25 ms 4964 KB Output is correct
5 Incorrect 195 ms 66628 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4948 KB Output is correct
2 Correct 180 ms 65752 KB Output is correct
3 Correct 208 ms 65744 KB Output is correct
4 Correct 177 ms 65840 KB Output is correct
5 Correct 23 ms 5148 KB Output is correct
6 Correct 166 ms 57300 KB Output is correct
7 Correct 186 ms 57744 KB Output is correct
8 Correct 182 ms 58076 KB Output is correct
9 Correct 202 ms 58208 KB Output is correct
10 Correct 216 ms 62632 KB Output is correct
11 Correct 230 ms 61984 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4948 KB Output is correct
2 Correct 180 ms 65752 KB Output is correct
3 Correct 208 ms 65744 KB Output is correct
4 Correct 177 ms 65840 KB Output is correct
5 Correct 23 ms 5148 KB Output is correct
6 Correct 166 ms 57300 KB Output is correct
7 Correct 186 ms 57744 KB Output is correct
8 Correct 182 ms 58076 KB Output is correct
9 Correct 202 ms 58208 KB Output is correct
10 Correct 216 ms 62632 KB Output is correct
11 Correct 230 ms 61984 KB Output is correct
12 Correct 23 ms 4960 KB Output is correct
13 Correct 259 ms 74856 KB Output is correct
14 Correct 222 ms 75096 KB Output is correct
15 Correct 245 ms 74956 KB Output is correct
16 Correct 251 ms 74956 KB Output is correct
17 Correct 30 ms 5068 KB Output is correct
18 Incorrect 209 ms 69424 KB Extra information in the output file
19 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5004 KB Output is correct
2 Correct 35 ms 6860 KB Output is correct
3 Correct 34 ms 6900 KB Output is correct
4 Correct 30 ms 7016 KB Output is correct
5 Correct 37 ms 7188 KB Output is correct
6 Correct 36 ms 6928 KB Output is correct
7 Correct 34 ms 5180 KB Output is correct
8 Correct 171 ms 57280 KB Output is correct
9 Correct 164 ms 57296 KB Output is correct
10 Correct 22 ms 5180 KB Output is correct
11 Correct 172 ms 65816 KB Output is correct
12 Correct 216 ms 65832 KB Output is correct
13 Correct 174 ms 65772 KB Output is correct
14 Correct 23 ms 5176 KB Output is correct
15 Correct 171 ms 57216 KB Output is correct
16 Correct 183 ms 57836 KB Output is correct
17 Correct 236 ms 58068 KB Output is correct
18 Correct 172 ms 58164 KB Output is correct
19 Correct 202 ms 62624 KB Output is correct
20 Correct 221 ms 61872 KB Output is correct
21 Correct 164 ms 57320 KB Output is correct
22 Correct 170 ms 57320 KB Output is correct
23 Correct 170 ms 57712 KB Output is correct
24 Correct 168 ms 57772 KB Output is correct
25 Correct 187 ms 59460 KB Output is correct
26 Correct 165 ms 57112 KB Output is correct
27 Correct 161 ms 57104 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5004 KB Output is correct
2 Correct 35 ms 6860 KB Output is correct
3 Correct 34 ms 6900 KB Output is correct
4 Correct 30 ms 7016 KB Output is correct
5 Correct 37 ms 7188 KB Output is correct
6 Correct 36 ms 6928 KB Output is correct
7 Correct 34 ms 5180 KB Output is correct
8 Correct 171 ms 57280 KB Output is correct
9 Correct 164 ms 57296 KB Output is correct
10 Correct 22 ms 5180 KB Output is correct
11 Correct 172 ms 65816 KB Output is correct
12 Correct 216 ms 65832 KB Output is correct
13 Correct 174 ms 65772 KB Output is correct
14 Correct 23 ms 5176 KB Output is correct
15 Correct 171 ms 57216 KB Output is correct
16 Correct 183 ms 57836 KB Output is correct
17 Correct 236 ms 58068 KB Output is correct
18 Correct 172 ms 58164 KB Output is correct
19 Correct 202 ms 62624 KB Output is correct
20 Correct 221 ms 61872 KB Output is correct
21 Correct 164 ms 57320 KB Output is correct
22 Correct 170 ms 57320 KB Output is correct
23 Correct 170 ms 57712 KB Output is correct
24 Correct 168 ms 57772 KB Output is correct
25 Correct 187 ms 59460 KB Output is correct
26 Correct 165 ms 57112 KB Output is correct
27 Correct 161 ms 57104 KB Output is correct
28 Correct 23 ms 5056 KB Output is correct
29 Correct 3407 ms 71308 KB Output is correct
30 Execution timed out 3567 ms 65404 KB Time limit exceeded
31 Halted 0 ms 0 KB -