Submission #936575

#	Time	Username	Problem	Language	Result	Execution time	Memory
936575		XXBabaProBerkay	Railway (BOI17_railway)	C++11	100 / 100	140 ms	27208 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, t = 0;
vector<int> d, ans, res, dpth;
vector<array<int, 20>> up;
vector<vector<pair<int, int>>> adj;

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

	d[k] = ++t;
	for (auto i : adj[k])
	{
		if (i.F == p)
			continue;

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

void dfs2(int k, int p)
{
	int x;
	for (auto i : adj[k])
	{
		if (i.F == p)
		{
			x = i.S;
			continue;
		}

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

	if (ans[k] >= K)
		res.push_back(x);
}

int kth_ancestor(int a, int k)
{
	for (int i = 0; i < 20; i++)
		if (k & (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];
}

bool comp(int a, int b)
{
	return d[a] < d[b];
}

int main()
{
	//cin.tie(0) -> sync_with_stdio(0);

	int n, m;
	cin >> n >> m >> K;
	d.resize(n + 1);
	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;
		vector<int> a(s);
		for (int &i : a) cin >> i;

		sort(a.begin(), a.end(), comp);

		ans[a[0]]++;
		int LCA = a[0];
		for (int i = 1; i < s; i++)
		{
			ans[a[i]]++;
			ans[lca(a[i], a[i - 1])]--;
			LCA = lca(LCA, a[i]);
		}

		ans[LCA]--;
	}

	dfs2(1, 0);

	sort(res.begin(), res.end());

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