제출 #857204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
857204		CongHao	Inside information (BOI21_servers)	C++14	100 / 100	227 ms	30244 KiB

servers

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

const int N = 12e4 + 5, numQ = N * 2;

vector<pair<int, int>> adj[N], Q[N];
vector<int> C[N];
char qr[numQ];
int n, q;

int ans[numQ];

bool rem[N];
int sz[N];

int dfs_size(int x, int p) {
	sz[x] = 1;
	for (const auto &elem: adj[x])
		if (elem.second != p && !rem[elem.second])
			sz[x] += dfs_size(elem.second, x);
	return sz[x];
}

int find_centroid(int x, int p, int n) {
	for (const auto &elem: adj[x])
		if (elem.second != p && !rem[elem.second] && sz[elem.second] > n / 2)
			return find_centroid(elem.second, x, n);
	return x;
}

struct FenwickTree {
	int BIT[numQ];
	vector<pair<int, int>> tmp;
	
	FenwickTree() = default;
	
	void update(int x, int w, bool reset = false) {
		if (!reset) tmp.emplace_back(x, w);
		for (; x <= q; x += x & -x)
			BIT[x] += w;
	}
	
	int pref(int x) const {
		int ans = 0;
		for (; x > 0; x -= x & -x)
			ans += BIT[x];
		return ans;
	}
	
	void reset() {
		while (!tmp.empty()) {
			auto S = tmp.back();
			tmp.pop_back();
			update(S.first, -S.second, true);
		}
	}
} fen;

int vs[N];

int rt = 0;
void dfs_calc(int x, int p, int d) { // decrease
	for (const auto &elem: Q[x]) 
		ans[elem.first] |= (vs[elem.second] && vs[elem.second] < elem.first);
	for (const int &id: C[x])
		if (id > rt) ans[id] += fen.pref(id - 1) + 1;
	for (const auto &elem: adj[x]) {
		int w, y; tie(w, y) = elem;
		if (y == p || rem[y] || d < w) continue;
		dfs_calc(y, x, w);
	}
}

vector<int> tmp;
void dfs_add(int x, int p, int d) { // increase
	vs[x] = d;
	tmp.emplace_back(x);
	fen.update(d, +1);
	for (const auto &elem: adj[x]) {
		int w, y; tie(w, y) = elem;
		if (y == p || rem[y] || d > w) continue;
		dfs_add(y, x, w);
	}
}

void centroid(int c) {
	c = find_centroid(c, 0, dfs_size(c, 0));
	rem[c] = true;
		
	for (const auto &elem: adj[c]) {
		int y, w; tie(w, y) = elem;
		if (rem[y]) continue;
		vs[c] = w;
		rt = w;
		dfs_calc(y, c, w); 
		dfs_add(y, c, w); 
	}
	
	for (const auto &elem: Q[c]) 
		ans[elem.first] |= (vs[elem.second] && vs[elem.second] < elem.first);
	for (const int &id: C[c])
		ans[id] += fen.pref(id - 1) + 1;
	
	fen.reset();
	vs[c] = 0;
	while (!tmp.empty()) {
		vs[tmp.back()] = 0;
		tmp.pop_back();
	}
	
	for (const auto &elem: adj[c]) {
		int y = elem.second;
		if (rem[y]) continue;
		centroid(y);
	}
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> q; q += n - 1;
	for (int i = 1; i <= q; i++) {
		cin >> qr[i];
		if (qr[i] == 'S') {
			int x, y;
			cin >> x >> y;
			adj[x].emplace_back(i, y);
			adj[y].emplace_back(i, x);
		} else if (qr[i] == 'Q') {
			int u, d;
			cin >> u >> d;
			if (u != d) Q[d].emplace_back(i, u);
			else ans[i] = true;
		} else {
			int d;
			cin >> d;
			C[d].emplace_back(i);
		}
	}
	for (int i = 1; i <= n; i++)
		sort(adj[i].begin(), adj[i].end(), greater<pair<int, int>>());
	centroid(1);
	for (int i = 1; i <= q; i++) {
		if (qr[i] == 'Q')
			cout << (ans[i] ? "yes" : "no") << '\n';
		else if (qr[i] == 'C')
			cout << ans[i] << '\n';
	}
	return 0;
}

• 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