oj.uz

Submission #542736

# Submission time Handle Problem Language Result Execution time Memory
542736 2022-03-27T19:34:56 Z skittles1412 Inside information (BOI21_servers) C++17
30 / 100
 3500 ms 63440 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) {
	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 36 ms 16492 KB Output is correct
2 Correct 51 ms 17412 KB Output is correct
3 Correct 48 ms 17484 KB Output is correct
4 Correct 48 ms 17580 KB Output is correct
5 Correct 45 ms 17672 KB Output is correct
6 Correct 47 ms 17664 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 16492 KB Output is correct
2 Correct 51 ms 17412 KB Output is correct
3 Correct 48 ms 17484 KB Output is correct
4 Correct 48 ms 17580 KB Output is correct
5 Correct 45 ms 17672 KB Output is correct
6 Correct 47 ms 17664 KB Output is correct
7 Correct 39 ms 16860 KB Output is correct
8 Correct 46 ms 18764 KB Output is correct
9 Correct 45 ms 18740 KB Output is correct
10 Correct 44 ms 18800 KB Output is correct
11 Correct 40 ms 19036 KB Output is correct
12 Correct 45 ms 18700 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 16496 KB Output is correct
2 Correct 214 ms 50384 KB Output is correct
3 Correct 223 ms 50380 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 16496 KB Output is correct
2 Correct 214 ms 50384 KB Output is correct
3 Correct 223 ms 50380 KB Output is correct
4 Correct 35 ms 16844 KB Output is correct
5 Correct 217 ms 51620 KB Output is correct
6 Correct 161 ms 54224 KB Output is correct
7 Correct 168 ms 54336 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 16460 KB Output is correct
2 Correct 149 ms 53680 KB Output is correct
3 Correct 148 ms 53724 KB Output is correct
4 Execution timed out 3580 ms 63388 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 16460 KB Output is correct
2 Correct 149 ms 53680 KB Output is correct
3 Correct 148 ms 53724 KB Output is correct
4 Execution timed out 3580 ms 63388 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 16456 KB Output is correct
2 Correct 285 ms 49152 KB Output is correct
3 Correct 176 ms 47600 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 16456 KB Output is correct
2 Correct 285 ms 49152 KB Output is correct
3 Correct 176 ms 47600 KB Output is correct
4 Correct 36 ms 16856 KB Output is correct
5 Correct 287 ms 51548 KB Output is correct
6 Correct 156 ms 52284 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 16404 KB Output is correct
2 Correct 148 ms 53712 KB Output is correct
3 Correct 153 ms 53736 KB Output is correct
4 Execution timed out 3594 ms 63436 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 16404 KB Output is correct
2 Correct 148 ms 53712 KB Output is correct
3 Correct 153 ms 53736 KB Output is correct
4 Execution timed out 3594 ms 63436 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 16472 KB Output is correct
2 Correct 50 ms 17436 KB Output is correct
3 Correct 46 ms 17496 KB Output is correct
4 Correct 49 ms 17596 KB Output is correct
5 Correct 47 ms 17740 KB Output is correct
6 Correct 48 ms 17572 KB Output is correct
7 Correct 35 ms 16468 KB Output is correct
8 Correct 229 ms 50380 KB Output is correct
9 Correct 222 ms 50464 KB Output is correct
10 Correct 33 ms 16408 KB Output is correct
11 Correct 143 ms 53720 KB Output is correct
12 Correct 150 ms 53708 KB Output is correct
13 Execution timed out 3595 ms 63440 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 16472 KB Output is correct
2 Correct 50 ms 17436 KB Output is correct
3 Correct 46 ms 17496 KB Output is correct
4 Correct 49 ms 17596 KB Output is correct
5 Correct 47 ms 17740 KB Output is correct
6 Correct 48 ms 17572 KB Output is correct
7 Correct 35 ms 16468 KB Output is correct
8 Correct 229 ms 50380 KB Output is correct
9 Correct 222 ms 50464 KB Output is correct
10 Correct 33 ms 16408 KB Output is correct
11 Correct 143 ms 53720 KB Output is correct
12 Correct 150 ms 53708 KB Output is correct
13 Execution timed out 3595 ms 63440 KB Time limit exceeded
14 Halted 0 ms 0 KB -