Submission #1097372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097372		Nguyen22cpp	Railway (BOI17_railway)	C++14	100 / 100	69 ms	23752 KiB

railway

// author : Nguyễn Trọng Nguyễn - ITK22 NBK
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair <int, int>
#define fi first
#define sc second
#define maxn 100000
#define inf (int)1e9
#define lg 16

int n, m, k;
vector <int> adj[maxn + 5];
ii egde[maxn + 5];
int dp[maxn + 5];
int timer = 0, tin[maxn + 5], tout[maxn + 5];
int up[lg + 5][maxn + 5];

void init () 
{
	cin >> n >> m >> k;
	for (int i = 1; i < n; i++) 
	{
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		egde[i] = {u, v};
	}
}

void dfs (int u = 1, int p = 1) 
{
	up[0][u] = p;
	tin[u] = ++timer;

	for (int i = 1; i <= lg; i++)
		up[i][u] = up[i - 1][up[i - 1][u]];

	for (auto v : adj[u])
		if (v != p) dfs(v, u);

	tout[u] = timer;
}

bool IsAncestor (int u, int v) 
{
	return tin[u] <= tin[v] and tout[u] >= tout[v];
}

int lca (int u, int v)
{
	if (IsAncestor(u, v)) return u;
	if (IsAncestor(v, u)) return v;

	for (int e = lg; e >= 0; e--) 
		if (!IsAncestor(up[e][u], v)) 
			u = up[e][u];

	return up[0][u];
}

void dfs2 (int u = 1) 
{
	for (auto v : adj[u]) 
	{
		if (v == up[0][u]) continue;
		dfs2(v);
		dp[u] += dp[v];
	}
}

bool cmp (int u, int v) 
{
	return tin[u] < tin[v];
}

void process () 
{
	dfs();

	while (m--) 
	{
		int x; cin >> x;
		vector <int> fix;

		while (x--) 
		{
			int u; cin >> u;
			fix.push_back(u);
		}

		sort(fix.begin(), fix.end(), cmp);

		int cur = fix[0];
		fix.push_back(cur);
		for (auto u : fix) 
		{
			dp[u]++, dp[cur]++;
			dp[lca(u, cur)] -= 2;
			cur = u;
		}
	}

	dfs2();

	vector <int> ans;
	for (int i = 1; i < n; i++) {
		int u, v; tie(u, v) = egde[i];
		int res = up[0][v] == u ? dp[v] : dp[u];
		if (res >= 2 * k) ans.push_back(i);
	}

	cout << (int)ans.size() << '\n';
	for (int v : ans) cout << v << ' ';
}

signed main () 
{
	cin.tie(0)->sync_with_stdio(false);
	
	

	init();
	process();

	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