oj.uz

Submission #542740

# Submission time Handle Problem Language Result Execution time Memory
542740 2022-03-27T20:10:09 Z skittles1412 Inside information (BOI21_servers) C++17
100 / 100
 432 ms 68588 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

namespace __gnu_pbds {
template <typename T, typename U = less<T>>
using ost = tree<T, null_type, U, rb_tree_tag, tree_order_statistics_node_update>;
}

using __gnu_pbds::ost;

using Q = const vector<tuple<char, int, int>>&;

void yno(bool b) {
	if (b) {
		cout << "yes" << endl;
	} else {
		cout << "no" << endl;
	}
}

const int maxn = 3e5, logn = 20;

vector<pair<int, int>> graph[maxn], qrs[maxn];
int t, tin[maxn], tout[maxn], par[maxn], parv[maxn], lift1[logn][maxn], lift2[logn][maxn],
	liftv1[logn][maxn], liftv2[logn][maxn], qans[maxn];

int siz[maxn];
bool vis[maxn];
ost<int> vals;

void pdfs(int u, int p = -1) {
	siz[u] = 1;
	for (auto& [v, _] : graph[u]) {
		if (v != p) {
			pdfs(v, u);
			siz[u] += siz[v];
		}
	}
}

template <bool ins>
void dfs1(int u, int prev = -1) {
	if (prev != -1) {
		if (ins) {
			vals.insert(prev);
		} else {
			vals.erase(prev);
		}
	}
	for (auto& [v, w] : graph[u]) {
		if (prev < w && !vis[v]) {
			dfs1<ins>(v, w);
		}
	}
}

void dfs2(int u, int prev) {
	static int qind = 0;
	for (auto& [x, i] : qrs[u]) {
		qind++;
		if (qind % int(1e6) == 0) {
			cerr << qind << endl;
		}
		qans[i] += int(vals.order_of_key(x));
	}
	for (auto& [v, w] : graph[u]) {
		if (prev > w && !vis[v]) {
			dfs2(v, w);
		}
	}
}

void qdfs(int u) {
	int targ = siz[u] / 2;
	while (true) {
		pair<int, int> opt;
		for (auto& [v, _] : graph[u]) {
			if (!vis[v]) {
				opt = max(opt, pair<int, int> {siz[v], v});
			}
		}
		if (opt.first > targ) {
			int v = opt.second;
			siz[u] -= siz[v];
			siz[v] += siz[u];
			u = v;
		} else {
			break;
		}
	}
	vals.clear();
	vis[u] = true;
	for (auto& [v, w] : graph[u]) {
		if (!vis[v]) {
			vals.insert(w);
			dfs2(v, w);
			dfs1<true>(v, w);
		}
	}
	for (auto& [x, i] : qrs[u]) {
		qans[i] += int(vals.order_of_key(x));
	}
	for (auto& [v, _] : graph[u]) {
		if (!vis[v]) {
			qdfs(v);
		}
	}
}

void qsolve() {
	pdfs(0);
	qdfs(0);
}

void dfs(int u, int p = -1) {
	tin[u] = t++;
	par[u] = lift1[0][u] = lift2[0][u] = p;
	for (auto& [v, w] : graph[u]) {
		if (v != p) {
			parv[v] = liftv1[0][v] = liftv2[0][v] = w;
			dfs(v, u);
		}
	}
	tout[u] = t++;
}

bool anc(int u, int v) {
	return tin[u] <= tin[v] && tout[v] <= tout[u];
}

template <typename T>
int blift(int u, int v, int lift[logn][maxn], int liftv[logn][maxn], const T& t) {
	if (anc(u, v)) {
		return u;
	}
	int prev = -1;
	for (int i = logn - 1; i >= 0; i--) {
		int p = lift[i][u];
		if (p != -1 && !anc(p, v)) {
			if (prev != -1 && !t(prev, parv[u])) {
				return -1;
			}
			prev = liftv[i][u];
			u = p;
		}
	}
	if (lift[0][u] == -1) {
		return -1;
	}
	if (prev != -1 && !t(prev, parv[u])) {
		return -1;
	}
	return u;
}

bool solve(int n, Q queries) {
	int ct = 0;
	for (int i = 0; i < sz(queries); i++) {
		auto& [c, u, v] = queries[i];
		if (c == 'S') {
			graph[u].emplace_back(v, ct);
			graph[v].emplace_back(u, ct);
			ct++;
		} else if (c == 'C') {
			qrs[u].emplace_back(ct, i);
		}
	}
	for (int i = 0; i < n; i++) {
		sort(begin(graph[i]), end(graph[i]), [&](const auto &a, const auto &b) -> bool {
			return a.second > b.second;
		});
	}
	dfs(0);
	// 1 - increasing upwards
	// 2 - decreasing upwards
	for (int i = 1; i < logn; i++) {
		for (int j = 0; j < n; j++) {
			{
				int p = lift1[i - 1][j];
				if (p != -1 && liftv1[i - 1][j] < parv[p]) {
					lift1[i][j] = lift1[i - 1][p];
					liftv1[i][j] = liftv1[i - 1][p];
				} else {
					lift1[i][j] = -1;
				}
			}
			{
				int p = lift2[i - 1][j];
				if (p != -1 && liftv2[i - 1][j] > parv[p]) {
					lift2[i][j] = lift2[i - 1][p];
					liftv2[i][j] = liftv2[i - 1][p];
				} else {
					lift2[i][j] = -1;
				}
			}
		}
	}
	qsolve();
	ct = -1;
	for (int i = 0; i < sz(queries); i++) {
		auto [c, u, v] = queries[i];
		if (c == 'S') {
			ct++;
		} else if (c == 'Q') {
			swap(u, v);
			if (u == v) {
				yno(true);
			} else {
				int cu = blift(u, v, lift1, liftv1, [&](int a, int b) -> bool {
					return a < b;
				});
				int cv = blift(v, u, lift2, liftv2, [&](int a, int b) -> bool {
					return b < a;
				});
				if (cu != -1 && cv != -1) {
					int lca = anc(u, v) ? u : par[cu];
					if (lca != (anc(v, u) ? v : par[cv])) {
						yno(false);
						continue;
					}
					assert(lca == (anc(v, u) ? v : par[cv]));
					if (anc(u, v)) {
						yno(parv[v] <= ct);
					} else if (anc(v, u)) {
						yno(parv[cu] <= ct);
					} else {
						yno(parv[cu] < parv[cv] && parv[v] <= ct);
					}
				} else {
					yno(false);
				}
			}
		} else {
			cout << 1 + qans[i] << endl;
		}
	}
	return true;
}

void solve() {
	int n, q;
	cin >> n >> q;
	vector<tuple<char, int, int>> queries(n + q - 1);
	for (auto& [c, u, v] : queries) {
		cin >> c;
		if (c != 'C') {
			cin >> u >> v;
			u--;
			v--;
		} else {
			cin >> u;
			u--;
		}
	}
	solve(n, queries);
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 16468 KB Output is correct
2 Correct 50 ms 17548 KB Output is correct
3 Correct 48 ms 17608 KB Output is correct
4 Correct 48 ms 17612 KB Output is correct
5 Correct 40 ms 17668 KB Output is correct
6 Correct 46 ms 17608 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 16468 KB Output is correct
2 Correct 50 ms 17548 KB Output is correct
3 Correct 48 ms 17608 KB Output is correct
4 Correct 48 ms 17612 KB Output is correct
5 Correct 40 ms 17668 KB Output is correct
6 Correct 46 ms 17608 KB Output is correct
7 Correct 39 ms 16824 KB Output is correct
8 Correct 46 ms 18764 KB Output is correct
9 Correct 45 ms 18636 KB Output is correct
10 Correct 50 ms 18792 KB Output is correct
11 Correct 41 ms 19084 KB Output is correct
12 Correct 47 ms 18756 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16468 KB Output is correct
2 Correct 220 ms 50896 KB Output is correct
3 Correct 219 ms 50856 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16468 KB Output is correct
2 Correct 220 ms 50896 KB Output is correct
3 Correct 219 ms 50856 KB Output is correct
4 Correct 36 ms 16764 KB Output is correct
5 Correct 210 ms 52032 KB Output is correct
6 Correct 154 ms 53048 KB Output is correct
7 Correct 177 ms 52996 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16468 KB Output is correct
2 Correct 169 ms 54124 KB Output is correct
3 Correct 161 ms 54176 KB Output is correct
4 Correct 293 ms 61684 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16468 KB Output is correct
2 Correct 169 ms 54124 KB Output is correct
3 Correct 161 ms 54176 KB Output is correct
4 Correct 293 ms 61684 KB Output is correct
5 Correct 32 ms 17732 KB Output is correct
6 Correct 182 ms 59532 KB Output is correct
7 Correct 282 ms 66156 KB Output is correct
8 Correct 177 ms 59968 KB Output is correct
9 Correct 183 ms 60028 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 16492 KB Output is correct
2 Correct 271 ms 49488 KB Output is correct
3 Correct 159 ms 48104 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 16492 KB Output is correct
2 Correct 271 ms 49488 KB Output is correct
3 Correct 159 ms 48104 KB Output is correct
4 Correct 38 ms 16776 KB Output is correct
5 Correct 289 ms 51936 KB Output is correct
6 Correct 171 ms 49868 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16404 KB Output is correct
2 Correct 164 ms 54232 KB Output is correct
3 Correct 169 ms 54240 KB Output is correct
4 Correct 302 ms 61644 KB Output is correct
5 Correct 37 ms 17300 KB Output is correct
6 Correct 271 ms 52744 KB Output is correct
7 Correct 160 ms 51332 KB Output is correct
8 Correct 214 ms 51704 KB Output is correct
9 Correct 194 ms 51760 KB Output is correct
10 Correct 262 ms 67652 KB Output is correct
11 Correct 296 ms 66180 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16404 KB Output is correct
2 Correct 164 ms 54232 KB Output is correct
3 Correct 169 ms 54240 KB Output is correct
4 Correct 302 ms 61644 KB Output is correct
5 Correct 37 ms 17300 KB Output is correct
6 Correct 271 ms 52744 KB Output is correct
7 Correct 160 ms 51332 KB Output is correct
8 Correct 214 ms 51704 KB Output is correct
9 Correct 194 ms 51760 KB Output is correct
10 Correct 262 ms 67652 KB Output is correct
11 Correct 296 ms 66180 KB Output is correct
12 Correct 34 ms 17628 KB Output is correct
13 Correct 179 ms 59548 KB Output is correct
14 Correct 290 ms 66148 KB Output is correct
15 Correct 179 ms 60072 KB Output is correct
16 Correct 191 ms 60024 KB Output is correct
17 Correct 35 ms 17648 KB Output is correct
18 Correct 281 ms 54940 KB Output is correct
19 Correct 159 ms 52812 KB Output is correct
20 Correct 196 ms 53648 KB Output is correct
21 Correct 191 ms 53848 KB Output is correct
22 Correct 291 ms 68164 KB Output is correct
23 Correct 432 ms 68544 KB Output is correct
24 Correct 373 ms 67728 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16456 KB Output is correct
2 Correct 50 ms 17516 KB Output is correct
3 Correct 47 ms 17600 KB Output is correct
4 Correct 49 ms 17612 KB Output is correct
5 Correct 42 ms 17680 KB Output is correct
6 Correct 46 ms 17652 KB Output is correct
7 Correct 34 ms 16460 KB Output is correct
8 Correct 226 ms 50880 KB Output is correct
9 Correct 227 ms 50904 KB Output is correct
10 Correct 35 ms 16436 KB Output is correct
11 Correct 192 ms 54232 KB Output is correct
12 Correct 163 ms 54232 KB Output is correct
13 Correct 282 ms 61644 KB Output is correct
14 Correct 36 ms 17364 KB Output is correct
15 Correct 267 ms 52804 KB Output is correct
16 Correct 159 ms 51396 KB Output is correct
17 Correct 208 ms 51796 KB Output is correct
18 Correct 184 ms 51772 KB Output is correct
19 Correct 248 ms 67784 KB Output is correct
20 Correct 291 ms 66180 KB Output is correct
21 Correct 207 ms 54664 KB Output is correct
22 Correct 215 ms 52524 KB Output is correct
23 Correct 213 ms 51404 KB Output is correct
24 Correct 211 ms 51648 KB Output is correct
25 Correct 228 ms 55432 KB Output is correct
26 Correct 170 ms 51136 KB Output is correct
27 Correct 161 ms 51012 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16456 KB Output is correct
2 Correct 50 ms 17516 KB Output is correct
3 Correct 47 ms 17600 KB Output is correct
4 Correct 49 ms 17612 KB Output is correct
5 Correct 42 ms 17680 KB Output is correct
6 Correct 46 ms 17652 KB Output is correct
7 Correct 34 ms 16460 KB Output is correct
8 Correct 226 ms 50880 KB Output is correct
9 Correct 227 ms 50904 KB Output is correct
10 Correct 35 ms 16436 KB Output is correct
11 Correct 192 ms 54232 KB Output is correct
12 Correct 163 ms 54232 KB Output is correct
13 Correct 282 ms 61644 KB Output is correct
14 Correct 36 ms 17364 KB Output is correct
15 Correct 267 ms 52804 KB Output is correct
16 Correct 159 ms 51396 KB Output is correct
17 Correct 208 ms 51796 KB Output is correct
18 Correct 184 ms 51772 KB Output is correct
19 Correct 248 ms 67784 KB Output is correct
20 Correct 291 ms 66180 KB Output is correct
21 Correct 207 ms 54664 KB Output is correct
22 Correct 215 ms 52524 KB Output is correct
23 Correct 213 ms 51404 KB Output is correct
24 Correct 211 ms 51648 KB Output is correct
25 Correct 228 ms 55432 KB Output is correct
26 Correct 170 ms 51136 KB Output is correct
27 Correct 161 ms 51012 KB Output is correct
28 Correct 38 ms 17744 KB Output is correct
29 Correct 47 ms 19944 KB Output is correct
30 Correct 44 ms 19796 KB Output is correct
31 Correct 46 ms 19940 KB Output is correct
32 Correct 42 ms 20152 KB Output is correct
33 Correct 44 ms 19792 KB Output is correct
34 Correct 36 ms 17740 KB Output is correct
35 Correct 217 ms 54708 KB Output is correct
36 Correct 159 ms 54708 KB Output is correct
37 Correct 176 ms 54836 KB Output is correct
38 Correct 32 ms 17740 KB Output is correct
39 Correct 179 ms 59600 KB Output is correct
40 Correct 275 ms 66124 KB Output is correct
41 Correct 176 ms 59972 KB Output is correct
42 Correct 178 ms 59984 KB Output is correct
43 Correct 36 ms 17740 KB Output is correct
44 Correct 281 ms 54904 KB Output is correct
45 Correct 163 ms 52784 KB Output is correct
46 Correct 190 ms 53592 KB Output is correct
47 Correct 188 ms 53800 KB Output is correct
48 Correct 301 ms 68120 KB Output is correct
49 Correct 376 ms 68588 KB Output is correct
50 Correct 349 ms 67760 KB Output is correct
51 Correct 174 ms 57068 KB Output is correct
52 Correct 204 ms 56692 KB Output is correct
53 Correct 185 ms 56268 KB Output is correct
54 Correct 173 ms 56868 KB Output is correct
55 Correct 150 ms 53904 KB Output is correct
56 Correct 173 ms 52552 KB Output is correct
57 Correct 185 ms 56556 KB Output is correct
58 Correct 217 ms 53424 KB Output is correct
59 Correct 168 ms 51908 KB Output is correct