Submission #1204875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204875		IBory	Inside information (BOI21_servers)	C++20	0 / 100	21 ms	21064 KiB

servers

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 240004;
vector<pii> G[MAX], Q1[MAX];
vector<int> Q2[MAX], A;
int Z[MAX], V[MAX], ans[MAX];

struct BIT {
	int T[MAX];
	void Update(int i, int v) {
		for (; i < MAX; i += i & -i) T[i] += v;
	}
	int Query(int L, int R) {
		int ret = 0; L--;
		for (; R; R -= R & -R) ret += T[R];
		for (; L; L -= L & -L) ret -= T[L];
		return ret;
	}
} T;

int GetSize(int cur, int prev) {
	A.push_back(cur);
	int& ret = Z[cur] = 1;
	for (auto [next, _] : G[cur]) {
		if (V[next] || next == prev) continue;
		ret += GetSize(next, cur);
	}
	return ret;
}

int GetCent(int cur, int prev, int lim) {
	for (auto [next, _] : G[cur]) {
		if (V[next] || next == prev) continue;
		if (lim <= Z[next]) return GetCent(next, cur, lim);
	}
	return cur;
}

vector<int> QR;
pii QE[MAX];
int QS[MAX];
void DFS1(int cur, int prev, int l1, int l2) {
	QE[cur] = {l1, l2};
	for (auto [next, v] : G[cur]) {
		if (V[next] || next == prev) continue;
		if (l2 < v) DFS1(next, cur, l1, v);
	}
}

void DFS2(int cur, int prev, int r1, int r2) {
	QS[cur] = r2;
	for (auto [e, id] : Q1[cur]) {
		if (r2 < QE[e].first && QE[e].second < id) ans[id] = -1;
	}
	for (auto [next, v] : G[cur]) {
		if (V[next] || next == prev) continue;
		if (v < r1) DFS2(next, cur, v, r2);
	}
}

void DFS3(int cur, int prev, int l) {
	QR.push_back(l);
	T.Update(l, 1);
	for (auto [next, v] : G[cur]) {
		if (V[next] || next == prev) continue;
		if (l < v) DFS3(next, cur, v);
	}
}

void DFS4(int cur, int prev, int r) {
	for (int id : Q2[cur]) {
		// cout << " + " << id << ' ' << 1 + T.Query(QS[cur] + 1, id) << '\n';
		ans[id] += 1 + T.Query(QS[cur] + 1, id);
	}
	for (auto [next, v] : G[cur]) {
		if (V[next] || next == prev) continue;
		if (v < r) DFS4(next, cur, v);
	}
}

void DnC(int cur) {
	cur = GetCent(cur, 0, GetSize(cur, 0) / 2);

	// Process (Q a d)
	QE[cur] = {1e9, 0};
	for (auto [next, v] : G[cur]) {
		if (V[next]) continue;
		DFS1(next, cur, v, v);
	}
	for (auto [next, v] : G[cur]) {
		if (V[next]) continue;
		DFS2(next, cur, v, v);
	}

	// Process (C d)
	vector<pii> ord;
	for (auto [next, v] : G[cur]) {
		if (V[next]) continue;
		ord.emplace_back(v, next);
	}
	sort(ord.begin(), ord.end(), greater<pii>());
	for (auto [v, next] : ord) {
		DFS4(next, cur, v);
		DFS3(next, cur, v);
	}

	for (int id : Q2[cur]) {
		ans[id] += T.Query(1, id);
		// cout << " + " << id << ' ' << T.Query(1, id) << '\n';
	}

	for (int n : A) {
		QE[n] = {0, 0};
		QS[n] = 1e9;
	}
	for (int p : QR) T.Update(p, -1);
	A.clear();
	QR.clear();

	V[cur] = 1;
	for (auto [next, _] : G[cur]) {
		if (V[next]) continue;
		DnC(next);
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, Q;
	cin >> N >> Q;

	for (int i = 1; i < N + Q; ++i) {
		char op;
		cin >> op;
		if (op == 'S') {
			int a, b;
			cin >> a >> b;
			G[a].emplace_back(b, i);
			G[b].emplace_back(a, i);
		}
		if (op == 'Q') {
			int a, b;
			cin >> a >> b;
			Q1[b].emplace_back(a, i);
			ans[i] = (a == b ? -1 : -2);
		}
		if (op == 'C') {
			int n;
			cin >> n;
			Q2[n].push_back(i);
			ans[i] = 1;
		}
	}

	memset(QS, 0x3f, sizeof(QS));
	DnC(1);

	for (int i = 1; i < N + Q; ++i) {
		if (!ans[i]) continue;
		if (ans[i] < 0) cout << (ans[i] == -1 ? "yes" : "no") << '\n';
		else cout << ans[i] << '\n';
	}
	return 0;
}

• Subtask 1-1: 0 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 0 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 0 / 5
• Subtask 3-2: 0 / 5
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 0 / 17
• Subtask 6-2: 0 / 18