Submission #1128040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128040		stdfloat	Railway (BOI17_railway)	C++20	100 / 100	185 ms	47876 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, tin, tout, ans;

vector<vector<int>> v, u, 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 = 19; i >= 0; i--)
		if (d[x] - (1 << i) >= d[y]) x = sp[x][i];

	if (x == y) return x;

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

	return sp[x][0];
}

set<int> dfs1(int x, int pr) {
	set<int> s(all(v[x]));
	for (auto [i, ind] : E[x]) {
		if (i != pr) {
			set<int> c = dfs1(i, x);
			if (k <= sz(c)) ans.push_back(ind);
		
			if (sz(s) < sz(c)) swap(s, c);

			for (auto j : c)
				s.insert(j);
		}
	}

	for (auto i : u[x])
		s.erase(i);

	return s;
}

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];
	}

	v.assign(n, {});
	u = v;
	for (int ii = 0; ii < m; ii++) {
		int z;
		cin >> z;

		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]]});
		}

		u[lc].push_back(ii);

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

			v[i].push_back(ii);
		}
	}

	dfs1(0, -1);

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

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