Submission #551491

#	Time	Username	Problem	Language	Result	Execution time	Memory
551491		sidon	Inside information (BOI21_servers)	C++17	50 / 100	285 ms	33248 KiB

servers

#include <bits/stdc++.h>
using namespace std;

const int Z = 1.2e5, B = 17;

int N, K, p[Z][B], up[Z][2], d[Z], pE[Z], res[Z];
vector<array<int, 2>> g[Z], h[Z];
vector<array<int, 4>> pQ;

void init(const int &u) {
	for(int i = 0; i + 1 < B; ++i)
		p[u][i+1] = p[p[u][i]][i];

	for(const auto &[v, i] : g[u]) if(v != p[u][0]) {
		p[v][0] = u;
		d[v] = d[u] + 1;
		pE[v] = i;

		if(pE[u] < i) {
			up[v][0] = up[u][0];
			up[v][1] = u;
		} else {
			up[v][0] = u;
			up[v][1] = up[u][1];
		}

		init(v);
	}
}

int _u, _v;

int lca(int u, int v) {
	bool swapped = 0;
	if((swapped = (d[u] < d[v]))) swap(u, v);

	if(d[u] > d[v]) {
		for(int i = B; i--; ) if((d[u] - d[v] - 1) & (1<<i))
			u = p[u][i];

		if(p[u][0] == v) {
			_u = u;
			return v;
		}
		u = p[u][0];
	}

	for(int i = B; i--; ) if(p[u][i] != p[v][i])
		u = p[u][i], v = p[v][i];
	if(swapped) swap(u, v);
	_u = u, _v = v;
	return p[u][0];
}

int main() {
	cin >> N >> K;

	for(int i {}, j {}; i < N - 1 + K; ++i) {
		char t; int u, v;
		cin >> t >> u; --u;
		if(t == 'S') {
			cin >> v; --v;
			g[u].push_back({v, i});
			g[v].push_back({u, i});
		}
		if(t == 'Q') {
			cin >> v; --v;
			pQ.push_back({j++, i, u, v});
		}

		if(t == 'C')
			h[u].push_back({j++, i});
	}

	init(0);

	for(const auto &[j, i, u, v] : pQ) {
		int w = lca(u, v), val = w == u ? pE[_u] : pE[u];

		if(w != u && w != v && pE[_u] < pE[_v])
			val = i;

		if(u == v || (max(d[up[u][0]], d[up[v][1]]) <= d[w] && val < i))
			res[j] = -1;
		else
			res[j] = -2;
	}

	for(int j = 0; j < K; ++j) {
		if(res[j] < 0) cout << (res[j] & 1 ? "yes" : "no");
		else assert(0);
		cout << '\n';
	}
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5