oj.uz

Submission #542734

# Submission time Handle Problem Language Result Execution time Memory
542734 2022-03-27T19:29:07 Z skittles1412 Inside information (BOI21_servers) C++17
17.5 / 100
 3500 ms 61972 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 = 2e5, 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) {
	for (auto& [x, i] : qrs[u]) {
		dbg(x, sz(vals));
		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]) {
			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() {
	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 40 ms 12636 KB Output is correct
2 Correct 57 ms 14152 KB Output is correct
3 Correct 53 ms 14136 KB Output is correct
4 Correct 68 ms 14156 KB Output is correct
5 Correct 44 ms 14336 KB Output is correct
6 Correct 50 ms 14228 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12636 KB Output is correct
2 Correct 57 ms 14152 KB Output is correct
3 Correct 53 ms 14136 KB Output is correct
4 Correct 68 ms 14156 KB Output is correct
5 Correct 44 ms 14336 KB Output is correct
6 Correct 50 ms 14228 KB Output is correct
7 Correct 40 ms 12956 KB Output is correct
8 Correct 54 ms 15176 KB Output is correct
9 Correct 60 ms 15016 KB Output is correct
10 Correct 50 ms 15144 KB Output is correct
11 Correct 44 ms 15384 KB Output is correct
12 Correct 52 ms 15016 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 12620 KB Output is correct
2 Correct 259 ms 48488 KB Output is correct
3 Correct 240 ms 48472 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 12620 KB Output is correct
2 Correct 259 ms 48488 KB Output is correct
3 Correct 240 ms 48472 KB Output is correct
4 Correct 55 ms 13032 KB Output is correct
5 Incorrect 268 ms 49416 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12616 KB Output is correct
2 Correct 166 ms 52228 KB Output is correct
3 Correct 167 ms 52244 KB Output is correct
4 Execution timed out 3535 ms 61948 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12616 KB Output is correct
2 Correct 166 ms 52228 KB Output is correct
3 Correct 167 ms 52244 KB Output is correct
4 Execution timed out 3535 ms 61948 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12624 KB Output is correct
2 Correct 340 ms 47584 KB Output is correct
3 Correct 189 ms 46156 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12624 KB Output is correct
2 Correct 340 ms 47584 KB Output is correct
3 Correct 189 ms 46156 KB Output is correct
4 Correct 37 ms 13004 KB Output is correct
5 Incorrect 363 ms 49612 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12620 KB Output is correct
2 Correct 162 ms 52332 KB Output is correct
3 Correct 195 ms 52324 KB Output is correct
4 Execution timed out 3598 ms 61928 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12620 KB Output is correct
2 Correct 162 ms 52332 KB Output is correct
3 Correct 195 ms 52324 KB Output is correct
4 Execution timed out 3598 ms 61928 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12620 KB Output is correct
2 Correct 57 ms 14100 KB Output is correct
3 Correct 58 ms 14156 KB Output is correct
4 Correct 56 ms 14248 KB Output is correct
5 Correct 43 ms 14356 KB Output is correct
6 Correct 53 ms 14292 KB Output is correct
7 Correct 37 ms 12628 KB Output is correct
8 Correct 247 ms 48540 KB Output is correct
9 Correct 242 ms 48476 KB Output is correct
10 Correct 33 ms 12656 KB Output is correct
11 Correct 172 ms 52288 KB Output is correct
12 Correct 165 ms 52344 KB Output is correct
13 Execution timed out 3590 ms 61972 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12620 KB Output is correct
2 Correct 57 ms 14100 KB Output is correct
3 Correct 58 ms 14156 KB Output is correct
4 Correct 56 ms 14248 KB Output is correct
5 Correct 43 ms 14356 KB Output is correct
6 Correct 53 ms 14292 KB Output is correct
7 Correct 37 ms 12628 KB Output is correct
8 Correct 247 ms 48540 KB Output is correct
9 Correct 242 ms 48476 KB Output is correct
10 Correct 33 ms 12656 KB Output is correct
11 Correct 172 ms 52288 KB Output is correct
12 Correct 165 ms 52344 KB Output is correct
13 Execution timed out 3590 ms 61972 KB Time limit exceeded
14 Halted 0 ms 0 KB -