Submission #1128035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128035		stdfloat	Railway (BOI17_railway)	C++20	0 / 100	97 ms	29372 KiB

railway

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

using ll = long long;

#define ff	first
#define ss	second
#define pii	pair<int, int>

#define sz(v)	(int)(v).size()
#define all(v)	(v).begin(), (v).end()

int k, tim;

vector<int> d, p, tin, tout, ans;

vector<vector<int>> sp;

vector<vector<pii>> E;

void dfs(int x, int pr) {
	sp[x][0] = pr;
	tin[x] = ++tim;
	if (~pr) d[x] = d[pr] + 1;

	for (auto [i, w] : E[x])
		if (i != pr) dfs(i, x);

	tout[x] = ++tim;
}

int lca(int x, int y) {
	if (d[x] < d[y]) swap(x, y);

	for (int i = 20; i >= 0; i--)
		if (d[x] - (1 << i) >= d[y]) x = sp[x][i];

	if (x == y) return x;

	for (int i = 20; i >= 0; i--) {
		if (sp[x][i] != sp[y][i]) {
			x = sp[x][i]; y = sp[y][i];
		}
	}

	return sp[x][0];
}

int dfs1(int x, int pr) {
	int sm = p[x];
	for (auto [i, ind] : E[x]) {
		if (i != pr) {
			int y = dfs1(i, x);
			if (k <= p[x] + y) ans.push_back(ind);

			sm += y;
		}
	}

	return sm;
}

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

	int n, m;
	cin >> n >> m >> k;

	E.assign(n, {});
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y; x--; y--;

		E[x].push_back({y, i});
		E[y].push_back({x, i});
	}

	d = tin = tout = vector<int>(n);
	sp.assign(n, vector<int>(20, -1));
	dfs(0, -1);

	for (int i = 1; i < 20; i++) {
		for (int j = 0; j < n; j++)
			if (~sp[j][i - 1]) sp[j][i] = sp[sp[j][i - 1]][i - 1];
	}

	p.assign(n, 0);
	while (m--) {
		int z;
		cin >> z;

		// cout << "\nz " << z << endl;

		int lc = 0;
		set<pii> s;
		vector<int> a(z);
		for (int i = 0; i < z; i++) {
			cin >> a[i]; a[i]--;

			lc = (i ? lca(lc, a[i]) : a[i]);
			s.insert({tin[a[i]], tout[a[i]]});

			// cout << a[i] + 1 << ' ' << lc + 1 << endl;
		}
		// cout << endl;

		int cnt = 0;
		for (auto i : a) {
			auto t = s.lower_bound({tin[i] + 1, 0});
			if (t != s.end() && (*t).ss < tout[i]) continue;

			// cout << i + 1 << ' ';

			cnt++;
			p[i]++;
		}

		// cout << endl << lc + 1 << ' ' << cnt << endl;

		p[lc] -= cnt - 1;
		if (~sp[lc][0]) p[sp[lc][0]]--;
	}

	// for (int i = 0; i < n; i++)
	// 	cout << p[i] << " \n"[i + 1 == n];

	dfs1(0, -1);

	sort(all(ans));
	cout << sz(ans) << '\n';
	for (auto i : ans)
		cout << i << ' ';
}

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