Submission #1096310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096310		Nguyen22cpp	Railway (BOI17_railway)	C++14	7 / 100	46 ms	25448 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

const int maxn = (int)1e5;
const int inf = (int)1e9;
const int lg = 16;

int n, m, k;
vector <int> adj[maxn + 5];
int timer = 0, tin[maxn + 5], tout[maxn + 5];
int up[lg + 5][maxn + 5];
int cnt[maxn + 5];
ii edge[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);
		edge[i] = {u, v};
	}
}

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

	up[0][u] = p;
	for (int e = 1; e <= lg; e++)
		up[e][u] = up[e - 1][up[e - 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, int p = 1) {
	for (auto v : adj[u]) {
		if (v == p) continue;
		dfs2(v, u);
		cnt[u] += cnt[v];
	}
}

void process () {
	dfs();

	for (int i = 1; i <= m; i++) {
		vector <ii> fix;

		int x; cin >> x;
		while (x--) {
			int u; cin >> u;
			fix.push_back({tin[u], u});
		}

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

		int cur = fix[0].sc;
		for (auto v : fix) {
			cnt[v.sc]++;
			cnt[lca(cur, v.sc)]--;
			cur = v.sc;				
		}
	}	

	dfs2();

	vector <int> node;
	for (int i = 1; i < n; i++) {
		int u, v; tie(u, v) = edge[i];
		int ans = up[0][u] == v ? cnt[u] : cnt[v];
		if (ans >= k) node.push_back(i);
	}

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

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

	init();
	process();

	return 0;
}

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