제출 #528470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528470		iliaM	Inside information (BOI21_servers)	C++17	100 / 100	563 ms	57372 KiB

servers

#include <bits/stdc++.h>
using namespace std;
#define cerr cerr << "DEBUG "

constexpr int N = 3e5 + 10;

int n, k;
vector<pair<int, int>> qp[N];
vector<int> qu[N];
vector<pair<int, int>> up, down;
vector<int> verts;
int sz[N];
vector<pair<int, int>> g[N];
bool used[N];
long long ans[N];
int mark[N];
pair<int, int> tmp[N];
bool has[N];

int centroid(int v, int p, int m) {
	has[v] = true;
	verts.push_back(v);
	int ret = 0, cool = 1;
	sz[v] = 1;
	for (auto &e : g[v]) {
		int u = e.first;
		if (u != p && !used[u]) {
			ret ^= ~centroid(u, v, m);
			cool &= sz[u] <= m / 2;
			sz[v] += sz[u];
		}
	}
	return cool && m - sz[v] <= m / 2 ? v : ~ret;
}


void dfs(int v, int p, int fe, int f, int s) {
	sz[v] = 1;
	if (~f) {
		for (auto &query : qu[v]) {
			if (fe > query) {
				continue;
			}
			up.push_back({fe, query});
		}
		mark[v] = fe;
	}
	if (~s) {
		down.push_back({fe, s});
		tmp[v] = make_pair(fe, s);
		assert(s >= fe);
	}
	for (auto &e : g[v]) {
		int u = e.first, w = e.second;
		if (u != p && !used[u]) {
			dfs(u, v, fe, f == -1 || w >= f ? -1 : w, s == -1 || w <= s ? -1 : w);
			sz[v] += sz[u];
		}
	}
}

int fen[N];

void update(int i, int x) {
	for (++i; i < N; i += i & -i) {
		fen[i] += x;
	}
}

int query(int i) {
	int ret = 0;
	for (++i; i > 0; i -= i & -i) {
		ret += fen[i];
	}
	return ret;
}

void solve() {
	static vector<int> vec[N];
	auto &a = up, &b = down;
	for (int i = 0; i < (int) b.size(); ++i) {
		vec[i].clear();
	}

	for (auto &x : a) {
		auto p = upper_bound(b.begin(), b.end(), make_pair(x.first, INT_MAX));
		ans[x.second]++; // for centroid
		if (p != b.end()) {
			vec[p - b.begin()].push_back(x.second);
		}
	}

	for (int i = (int) b.size() - 1; i >= 0; --i) {
		update(b[i].second, +1);
		for (auto &x : vec[i]) {
			ans[x] += query(x);
		}
	}
	for (auto &x : b) {
		update(x.second, -1);
	}
}

void decompose(int v, int m) {
	int cent = centroid(v, -1, m);
	
	up.clear();
	down.clear();
	
	sz[cent] = 1;
	for (auto &e : g[cent]) {
		int u = e.first, w = e.second;
		if (!used[u]) {
			dfs(u, cent, w, w, w);
			sz[cent] += sz[u];
		}
	}
	
	// calc for pairs in subtrees
	sort(down.begin(), down.end());
	solve();
	
	assert((int) verts.size() == sz[cent]);

	for (auto &u : verts) {
		for (auto &query : qp[u]) {
			if (!has[query.first]) {
				continue;
			}
			if (u == cent) {
				ans[query.second] += query.first == u ||
					(tmp[query.first].second < query.second);
			} else if (~mark[u]) {
				if (query.first == cent) {
					ans[query.second] += mark[u] < query.second;
				} else {
					ans[query.second] += mark[u] < tmp[query.first].first &&
						tmp[query.first].second < query.second;
				}
			}
		}
	}

	// calc for pairs from centroid
	for (auto &x : down) {
		update(x.second, +1);
	}
	for (auto &que : qu[cent]) {
		ans[que] += 1 + query(que);
	}
	for (auto &x : down) {
		update(x.second, -1);
	}

	for (auto &u : verts) {
		mark[u] = -1;
		tmp[u] = make_pair(-1, INT_MAX);
		has[u] = false;
	}
	verts.clear();
	used[cent] = true;
	for (auto &e : g[cent]) {
		int u = e.first;
		if (!used[u]) {
			decompose(u, sz[u]);
		}
	}
}

int qtype[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	memset(mark, -1, sizeof(mark));
	for (int i = 0; i < N; ++i) {
		tmp[i] = make_pair(-1, INT_MAX);
	}

	cin >> n >> k;
	for (int i = 0; i < n + k - 1; ++i) {
		char op;
		cin >> op;
		int v;
		cin >> v;
		--v;
		if (op == 'S') {
			int u;
			cin >> u;
			--u;
			g[v].push_back({u, i});
			g[u].push_back({v, i});
		} else if (op == 'Q') {
			qtype[i] = 1;
			int u;
			cin >> u;
			--u;
			qp[u].push_back({v, i});
		} else {
			qtype[i] = 2;
			qu[v].push_back(i);
		}
	}

	decompose(0, n);
	
	for (int i = 0; i < n + k - 1; ++i) {
		if (qtype[i] == 1) {
			cout << (ans[i] ? "yes" : "no") << '\n';
		} else if (qtype[i] == 2) {
			cout << ans[i] << '\n';
		}
	}
}

• 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