Submission #548860

#	Time	Username	Problem	Language	Result	Execution time	Memory
548860		lorenzoferrari	Railway (BOI17_railway)	C++17	100 / 100	196 ms	50032 KiB

railway

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

const int LOG = 18;

struct Lca {
	int n;
	vector<int> dep;
	vector<vector<int>> up;
	Lca(vector<int> par, vector<int> dep) : n(par.size()), dep(dep) {
		up.assign(n, vector<int>(LOG));
		for (int i = 0; i < n; ++i) {
			up[i][0] = par[i];
		}
		for (int i = 1; i < LOG; ++i) {
			for (int j = 0; j < n; ++j) {
				up[j][i] = up[up[j][i-1]][i-1];
			}
		}
	}
	int lift(int v, int k) {
		for (int i = LOG-1; i >= 0; --i) {
			if (k & (1 << i)) {
				v = up[v][i];
				k -= 1 << i;
			}
		}
		return v;
	}
	int lca(int a, int b) {
		if (dep[a] > dep[b]) swap(a, b);
		b = lift(b, dep[b] - dep[a]);
		for (int i = LOG-1; i >= 0; --i) {
			if (up[a][i] != up[b][i]) {
				a = up[a][i];
				b = up[b][i];
			}
		}
		if (a == b) return a;
		return up[a][0];
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n; cin >> n;
	int m; cin >> m;
	int k; cin >> k;
	vector<array<int, 2>> e;
	vector<vector<int>> adj(n);
	for (int i = 0, a, b; i < n-1; ++i) {
		cin >> a >> b; --a; --b;
		e.push_back({a, b});
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	vector<int> par(n), dep(n);
	auto dfs = [&](auto&& self, int v) -> void {
		for (int u : adj[v]) {
			if (u == par[v]) continue;
			dep[u] = dep[v] + 1;
			par[u] = v;
			self(self, u);
		}
	};
	dfs(dfs, 0);
	Lca lca(par, dep);
	vector<vector<array<int, 2>>> actions(n);
	for (int i = 0; i < m; ++i) {
		int s; cin >> s;
		int l; cin >> l; --l;
		for (int j = 1, a; j < s; ++j) {
			cin >> a; --a;
			int nl = lca.lca(l, a);
			actions[a].push_back({i, 1});
			actions[l].push_back({i, 1});
			actions[nl].push_back({i, 0});
			l = nl;
		}
	}
	vector<int> cnt(n);
	auto solve = [&](auto&& self, int v) -> set<int> {
		set<int> s;
		for (int u : adj[v]) {
			if (u == par[v]) continue;
			auto ss = self(self, u);
			if (ss.size() > s.size()) swap(s, ss);
			for (int i : ss) s.insert(i);
		}
		for (auto [a, b] : actions[v]) {
			if (b == 1) s.insert(a);
			else {
				auto it = s.find(a);
				if (it != s.end()) {
					s.erase(it);
				}
			}
		}
		cnt[v] = s.size();
		return s;
	};
	solve(solve, 0);
	vector<int> ans;
	for (int i = 0; i < n-1; ++i) {
		auto [a, b] = e[i];
		if (par[a] == b && cnt[a] >= k) ans.push_back(i+1);
		else if (par[b] == a && cnt[b] >= k) ans.push_back(i+1);
	}
	cout << ans.size() << "\n";
	for (int i : ans) {
		cout << i << " ";
	}
	cout << "\n";
}

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