Submission #1251209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251209		kaiboy	Railway (BOI17_railway)	C++20	100 / 100	114 ms	15884 KiB

railway

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 100000;

int ij[N - 1];
vector<int> eh[N];
int ta[N], tb[N];
int dd[N], pp[N], qq[N];
int ii[N], ft[N], kk[N];

void dfs(int p, int i, int d) {
	static int t;
	ta[i] = t++;
	dd[i] = d++;
	pp[i] = qq[i] = p;
	if (dd[p] - dd[qq[p]] == dd[qq[p]] - dd[qq[qq[p]]])
		qq[i] = qq[qq[p]];
	for (int h : eh[i]) {
		int j = i ^ ij[h];
		if (j != p)
			dfs(i, j, d);
	}
	tb[i] = t;
}

void update(int i, int n, int a) {
	for ( ; i < n; i |= i + 1)
		ft[i] += a;
}

int query(int i) {
	int a = 0;
	for ( ; i >= 0; i &= i + 1, i--)
		a += ft[i];
	return a;
}

int lca(int i, int j) {
	if (dd[i] < dd[j])
		swap(i, j);
	while (dd[i] > dd[j])
		if (dd[qq[i]] > dd[j])
			i = qq[i];
		else
			i = pp[i];
	while (i != j)
		if (qq[i] != qq[j])
			i = qq[i], j = qq[j];
		else
			i = pp[i], j = pp[j];
	return i;
}

bool check(int i) {
	return query(tb[i] - 1) - query(ta[i] - 1);
}

int search(int i) {
	while (!check(i))
		if (!check(qq[i]))
			i = qq[i];
		else
			i = pp[i];
	return i;
}

int dfs_(int h_, int i, int k_) {
	int k = kk[i];
	for (int h : eh[i])
		if (h != h_)
			k += dfs_(h, i ^ ij[h], k_);
	if (i && k >= k_)
		ij[h_] = -1;
	return k;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, q, k; cin >> n >> q >> k;
	for (int h = 0; h < n - 1; h++) {
		int i, j; cin >> i >> j, i--, j--;
		ij[h] = i ^ j;
		eh[i].push_back(h);
		eh[j].push_back(h);
	}
	dfs(0, 0, 0);
	while (q--) {
		int m; cin >> m;
		for (int h = 0; h < m; h++)
			cin >> ii[h], ii[h]--;
		int a = ii[0];
		update(ta[a], n, 1);
		for (int h = 1; h < m; h++) {
			int i = ii[h];
			kk[a]++, kk[a = lca(a, i)]--;
			kk[i]++, kk[search(i)]--;
			update(ta[i], n, 1);
		}
		for (int h = 0; h < m; h++)
			update(ta[ii[h]], n, -1);
	}
	dfs_(-1, 0, k);
	int x = 0;
	for (int h = 0; h < n - 1; h++)
		if (ij[h] == -1)
			x++;
	cout << x << '\n';
	for (int h = 0; h < n - 1; h++)
		if (ij[h] == -1)
			cout << h + 1 << ' ';
	cout << '\n';
	return 0;
}

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