제출 #542740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
542740		skittles1412	Inside information (BOI21_servers)	C++17	100 / 100	432 ms	68588 KiB

servers

#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
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5