Submission #997342

#	Time	Username	Problem	Language	Result	Execution time	Memory
997342		goats_9	Railway (BOI17_railway)	C++17	36 / 100	58 ms	29316 KiB

railway

/* Author: goats_9 */

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

using ll = long long;
const int LOG = 18;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m, k;
	cin >> n >> m >> k;
	vector<int> depth(n + 1), maj(n + 1), ans(n), in(n + 1), out(n + 1);
	vector<array<int, 2>> edges(n);
	vector<vector<array<int, 2>>> adj(n + 1, vector<array<int, 2>>());
	vector<array<int, LOG>> par(n + 1);
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		edges[i] = {u, v};
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
	}
	int cnt = 0;
	function<void(int, int)> dfs = [&] (int u, int p) {
		par[u][0] = p;
		for (int i = 1; i < LOG; i++) par[u][i] = par[par[u][i - 1]][i - 1];
		depth[u] = depth[p] + 1;
		in[u] = cnt++;
		for (auto [v, _] : adj[u]) {
			if (v == p) continue;
			dfs(v, u);
		}
		out[u] = cnt++;
	};
	auto is_anc = [&] (int u, int v) -> bool {
		return in[u] <= in[v] && out[v] <= out[u];
	};
	auto lca = [&] (int u, int v) -> int {
		if (depth[u] > depth[v]) swap(u, v);
		if (is_anc(u, v)) return u;
		int d = depth[v] - depth[u];
		for (int i = LOG - 1; i >= 0; i--) {
			if (d&(1<<i)) v = par[v][i];
		}
		for (int i = LOG - 1; i >= 0; i--) {
			if (par[u][i] != par[v][i]) {
				u = par[u][i];
				v = par[v][i];
			}
		}
		return par[u][0];
	};
	function <void(int, int, int)> dfs2 = [&] (int u, int p, int idx) {
		for (auto [v, j] : adj[u]) {
			if (v == p) continue;
			dfs2(v, u, j);
			maj[u] += maj[v];
		}
		ans[idx] = maj[u];
	};
	dfs(1, 0);
	while (m--) {
		int sz;
		cin >> sz;
		set<array<int, 3>> st;
		while (sz--) {
			int x;
			cin >> x;
			st.insert({-depth[x], in[x], x});
		}
		while (st.size() > 1) {
			auto [du, inu, u] = *st.begin();
			st.erase(st.begin());
			auto [dv, inv, v] = *st.begin();
			st.erase(st.begin());
			int w = lca(u, v);
			++maj[u], ++maj[v];
			maj[w] -= 2;
			st.insert({-depth[w], in[w], w});
		}
	}
	dfs2(1, 0, 0);
	vector<int> res;
	for (int i = 1; i < n; i++) {
		if (ans[i] >= k) res.push_back(i);
	}
	cout << res.size() << '\n';
	for (auto u : res) cout << u << ' ';
	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25