제출 #1264002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264002		EntityPlantt	Railway (BOI17_railway)	C++20	36 / 100	57 ms	21696 KiB

railway

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 1e5, D = 19;
vector<pair<int, int>> g[N];
int ans[N], lz[N], bl[D][N], d[N];

void dfs(int u) {
	for (auto &[v, e] : g[u]) {
		if (v == bl[0][u]) continue;
		bl[0][v] = u;
		d[v] = d[u] + 1;
		dfs(v);
	}
}
void dfs2(int u, int y) {
	for (auto &[v, e] : g[u]) {
		if (e == y) continue;
		dfs2(v, e);
		lz[u] += lz[v];
	}
	ans[y] = lz[u];
}
int lca(int u, int v) {
	if (d[u] < d[v]) swap(u, v);
	for (int i = D - 1; i >= 0; i--) if (d[u] - d[v] >= 1 << i) u = bl[i][u];
	if (u == v) return u;
	for (int i = D - 1; i >= 0; i--) if (bl[i][u] != bl[i][v]) u = bl[i][u], v = bl[i][v];
	return bl[0][u];
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, q, k;
	cin >> n >> q >> k;
	for (int i = 1, a, b; i < n; i++) {
		cin >> a >> b;
		g[--a].push_back({--b, i});
		g[b].push_back({a, i});
	}
	dfs(0);
	for (int j = 1; j < D; j++) {
		#pragma GCC ivdep
		for (int i = 0; i < n; i++) bl[j][i] = bl[j - 1][bl[j - 1][i]];
	}
	while (q--) {
		int s, first, last, x;
		cin >> s >> first;
		++lz[last = --first];
		for (int i = 1; i < s; i++) {
			cin >> x;
			++lz[--x];
			--lz[lca(last, x)];
			last = x;
		}
		--lz[lca(x, first)];
	}
	dfs2(0, 0);
	vector<int> r;
	for (int i = 1; i < n; i++) if (ans[i] >= k) r.push_back(i);
	cout << r.size() << '\n';
	for (int &i : r) cout << i << ' ';
}

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