Submission #935183

#	Time	Username	Problem	Language	Result	Execution time	Memory
935183		XXBabaProBerkay	Railway (BOI17_railway)	C++11	0 / 100	72 ms	25016 KiB

railway

#include <bits/stdc++.h>
using namespace std;
 
#define F first
#define S second
 
using ll = long long;
 
const int INF = 1e9 + 7;

int K;
vector<int> ans, res, dpth;
vector<vector<pair<int, int>>> adj;
vector<array<int, 20>> up;

void dfs(int k, int p)
{
	up[k][0] = p;
	for (int i = 1; i < 20; i++)
		up[k][i] = up[up[k][i - 1]][i - 1];

	for (pair<int, int> i : adj[k])
	{
		if (i.F == p)
			continue;

		dpth[i.F] = dpth[k] + 1;
		dfs(i.F, k);
	}
}

void dfs2(int k, int p)
{
	for (pair<int, int> i : adj[k])
	{
		if (i.F == p)
			continue;

		dfs2(i.F, k);
		ans[k] += ans[i.F];

		if (min(ans[k], ans[i.F]) >= K)
			res.push_back(i.S);
	}
}

int kth_ancestor(int a, int x)
{
	for (int i = 0; i < 20; i++)
		if (x & (1 << i))
			a = up[a][i];

	return a;
}

int lca(int a, int b)
{
	if (dpth[a] < dpth[b])
		swap(a, b);

	a = kth_ancestor(a, dpth[a] - dpth[b]);

	if (a == b)
		return a;

	for (int i = 19; i >= 0; i--)
		if (up[a][i] != up[b][i])
			a = up[a][i], b = up[b][i];

	return up[a][0];
}

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

	int n, m;
	cin >> n >> m >> K;
	up.resize(n + 1);
	adj.resize(n + 1);
	ans.resize(n + 1);
	dpth.resize(n + 1);
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		adj[a].emplace_back(b, i + 1);
		adj[b].emplace_back(a, i + 1);
	}

	dfs(1, 0);

	while (m--)
	{
		int s;
		cin >> s;
		int LCA = 0;
		for (int i = 0; i < s; i++)
		{
			int x;
			cin >> x;
			ans[x]++;
			if (i == 0)
				LCA = x;
			else
				LCA = lca(LCA, x);
		}

		ans[LCA] -= s - 1;
		ans[up[LCA][0]]--;
	}

	dfs2(1, 0);

	sort(res.begin(), res.end());
	cout << res.size() << '\n';
	for (int i : res)
		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