Submission #1036768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036768		sinatbtfard	Railway (BOI17_railway)	C++17	100 / 100	90 ms	24524 KiB

railway

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int maxn = 1e5 + 1, maxLg = 20;

int n, q, k, timer, a[maxn], h[maxn], st[maxn], fn[maxn], par[maxn][maxLg];
vector <pair <int, int>> adj[maxn], check;
vector <int> res;

void dfs (int v, int p = 0){
	st[v] = timer++;
	par[v][0] = p;
	for (int i = 1; i < maxLg; i++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	for (auto [u, ind] : adj[v]){
		if (u != p){
			h[u] = h[v] + 1;
			dfs(u, v);
		}
	}
	fn[v] = timer++;
}

int lca (int x, int y){
	if (h[x] < h[y])
		swap(x, y);
	if (st[x] <= st[y] && fn[x] >= fn[y])
		return x;
	for (int i = maxLg - 1; i >= 0; i--){
		if (par[x][i] == 0)
			continue;
		int u = par[x][i];
		if (!(st[u] <= st[y] && fn[u] >= fn[y]))
			x = u;
	}
	return par[x][0];
}

void dfs2 (int v, int ind, int p = 0){
	for (auto [u, i] : adj[v])
		if (u != p)
			dfs2(u, i, v);
	a[p] += a[v];
	if (a[v] >= 2 * k && ind > -1)
		res.pb(ind);
}

int main (){
	ios_base::sync_with_stdio(0);
	cin >> n >> q >> k;
	for (int x, y, i = 0; i < n - 1; i++)
		cin >> x >> y,
		adj[x].pb({y, i}),
		adj[y].pb({x, i});
	dfs(1);
	for (int s, i = 0; i < q; i++){
		cin >> s;
		for (int x, j = 0; j < s; j++)
			cin >> x,
			check.pb({st[x], x});
		sort(check.begin(), check.end());
		for (int j = 0; j < s; j++){
			auto [v, u] = make_pair(check[j].second, check[(j + 1) % s].second);
			a[v]++;
			a[u]++;
			a[lca(v, u)] -= 2;
		}
		check.clear();
	}
	dfs2(1, -1);
	sort(res.begin(), res.end());
	cout << res.size() << '\n';
	for (auto e : res)
		cout << e + 1 << " ";
}

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