Submission #511310

#	Time	Username	Problem	Language	Result	Execution time	Memory
511310		Elegia	Inside information (BOI21_servers)	C++17	100 / 100	481 ms	33416 KiB

servers

#include <cmath>

#include <algorithm>
#include <stack>
#include <bitset>
#include <numeric>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>

using ull = unsigned long long;

using std::vector;
using std::pair;
using std::function;
using std::ios;
using std::cin;
using std::cout;

const int _ = 120007;

int N;
char opt[_];
int x[_], y[_], t[_], ans[_], siz[_], sprt[_], pw[_];
bool vis[_], inc[_], dec[_];
vector<pair<int, int>> G[_];
vector<int> sub[_];

int fw[_];
void ch(int k, int x) { for (; k <= N; k += k & -k) fw[k] += x; }
int qry(int k) { int ret = 0; for (; k; k &= k - 1) ret += fw[k]; return ret; }

void solve(int rt, const vector<int>& query) {
	function<void(int, int)> dfs = [&](int u, int p) {
		siz[u] = 1;
		for (auto [v, w] : G[u]) if (!vis[v] && v != p) {
			dfs(v, u); siz[u] += siz[v];
		}
	};
	dfs(rt, 0);
	function<int(int)> cent = [&](int u) {
		for (auto [v, w] : G[u]) if (!vis[v] && siz[v] < siz[u] && siz[v] * 2 >= siz[rt])
			return cent(v);
		return u;
	};
	vis[rt = cent(rt)] = true;
	inc[rt] = dec[rt] = true; sprt[rt] = pw[rt] = 0;
	vector<pair<int, int>> pt;
	function<void(int, int)> dfs2 = [&](int u, int p) {
		if (dec[u]) pt.emplace_back(pw[sprt[u]], -pw[u]);
		for (auto [v, w] : G[u]) if (!vis[v] && v != p) {
			sprt[v] = sprt[u]; pw[v] = w;
			inc[v] = inc[u] && w < pw[u];
			dec[v] = dec[u] && w > pw[u];
			dfs2(v, u);
		}
	};
	for (auto [v, w] : G[rt]) if (!vis[v]) {
		sprt[v] = v; pw[v] = w; inc[v] = dec[v] = true;
		dfs2(v, rt);
	}
	for (int i : query)
		if (opt[i] == 'Q') {
			if (x[i] == y[i]) continue;
			if (sprt[x[i]] && sprt[y[i]] && sprt[x[i]] == sprt[y[i]]) {
				sub[sprt[x[i]]].push_back(i);
				continue;
			}
			if (!inc[x[i]] || !dec[y[i]]) { ans[i] = 0; continue; }
			if (sprt[x[i]] && sprt[y[i]] && pw[sprt[x[i]]] > pw[sprt[y[i]]]) ans[i] = 0;
			int lst = pw[y[i]]; if (!lst) lst = pw[sprt[x[i]]];
			ans[i] &= lst <= t[i];
		} else {
			if (!inc[x[i]]) {
				if (x[i] != rt) sub[sprt[x[i]]].push_back(i);
				continue;
			}
			if (x[i] != rt) {
				int sp = sprt[x[i]];
				pt.emplace_back(pw[sp], i);
				ans[i] += pw[sp] <= t[i];
				sub[sp].push_back(i);
			} else {
				pt.emplace_back(0, i);
				++ans[i];
			}
		}
	sort(pt.begin(), pt.end(), std::greater<pair<int, int>>());
	for (auto [i, j] : pt) {
		if (j < 0) ch(-j, 1);
		else ans[j] += qry(t[j]);
	}
	for (auto [i, j] : pt) if (j < 0) ch(-j, -1);
	for (auto [v, w] : G[rt]) if (!vis[v]) {
		vector<int> tmp; swap(tmp, sub[v]);
		solve(v, tmp);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	int K; cin >> N >> K;
	int clo = 0, cnt = 0;
	for (int rep = 0; rep != N + K - 1; ++rep) {
		char o; int u, v; cin >> o >> u;
		if (o == 'S') {
			cin >> v; ++clo;
			G[u].emplace_back(v, clo);
			G[v].emplace_back(u, clo);
		} else {
			++cnt;
			if (o == 'Q') { cin >> v; std::swap(u, v); ans[cnt] = 1; }
			opt[cnt] = o; x[cnt] = u; y[cnt] = v; t[cnt] = clo;
		}
	}
	vector<int> all(K); iota(all.begin(), all.end(), 1);
	solve(1, all);
	for (int i = 1; i <= K; ++i)
		if (opt[i] == 'Q') cout << (ans[i] ? "yes\n" : "no\n");
		else 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