Submission #997408

#	Time	Username	Problem	Language	Result	Execution time	Memory
997408		goats_9	Railway (BOI17_railway)	C++17	52 / 100	87 ms	28108 KiB

railway

/* Author: goats_9 */

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

#define LSOne(s) (s & -(s))

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

class BIT {
	int n;
	vector<int> ft;

public:
	BIT(int _n) : n(_n), ft(n + 1, 0) {}

	void update(int i, int v) {
		for (; i <= n; i += LSOne(i)) ft[i] += v;
	}

	int query(int l, int r) {
		int ans = 0;
		for (; r; r -= LSOne(r)) ans += ft[r];
		for (l--; l; l -= LSOne(l)) ans -= ft[l];
		return ans;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m, k;
	cin >> n >> m >> k;
	vector<int> in(n + 1), out(n + 1), par_edge(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, int)> dfs = [&] (int u, int p, int pe) {
		par[u][0] = p;
		for (int i = 1; i < LOG; i++) par[u][i] = par[par[u][i - 1]][i - 1];
		par_edge[u] = pe;
		in[u] = ++cnt;
		for (auto [v, j] : adj[u]) {
			if (v == p) continue;
			dfs(v, u, j);
		}
		out[u] = cnt;
	};
	dfs(1, 0, 0);
	BIT ft(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 (is_anc(u, v)) return u;
		for (int i = LOG - 1; i >= 0; i--) {
			if (par[u][i] && !is_anc(par[u][i], v)) u = par[u][i];
		}
		return par[u][0];
	};
	while (m--) {
		int s;
		cin >> s;
		vector<int> b(s);
		for (int i = 0; i < s; i++) cin >> b[i];
		sort(b.begin(), b.end(), [&] (int u, int v) { return in[u] < in[v]; });
		b.push_back(b.front());
		for (int i = 0; i < s; i++) {
			int u = b[i], v = b[i + 1];
			int w = lca(u, v);
			ft.update(in[u], 1);
			ft.update(in[v], 1);
			ft.update(in[w], -2);
		}
	}
	vector<int> res;
	for (int i = 2; i < n; i++) {
		if (ft.query(in[i], out[i]) >= 2*k) res.push_back(par_edge[i]);
	}
	sort(res.begin(), res.end());
	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: 16 / 16
• Subtask 6: 0 / 25