Submission #1288822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288822		limits	Railway (BOI17_railway)	C++20	100 / 100	53 ms	22468 KiB

railway

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define f0r(i, n) for (auto i = 0; i < (n); ++i)
#define fnr(i, n, k) for (auto i = (n); i < (k); ++i)
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define F first
#define S second
#define ctn(x) cout << x << '\n'
#define forl(a, l) for (auto a : l)
#define ctl(l) for (auto &a : (l)) cout << a << ' '; cout << '\n';
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define ub(v, x) (upper_bound(all(v), x) - begin(v))
#define pq priority_queue

template <class T>
using V = vector<T>;
using ll = long long;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using Adj = V<vi>;
using vvi = V<vi>;

const int N = 1e5+5;
const int LG = 17;
int par[LG][N], dep[N], tin[N], wt[N], tim = 0;
V<pi> G[N];

void dfs(int v) {
	tin[v] = tim++;
	for (auto &[c, _]: G[v]) if (c != par[0][v]) {
		dep[c] = dep[v] + 1;
		par[0][c] = v;
		fnr(i, 1, LG) par[i][c] = par[i-1][par[i-1][c]];
		dfs(c);
	}
}
int kth_anc(int v, int k) {
	f0r(i, LG) if ((k >> i) & 1) v = par[i][v];
	return v;
}
int lca(int u, int v) {
	if (dep[u] > dep[v]) swap(u, v);
	v = kth_anc(v, dep[v] - dep[u]);
	if (u == v) return u;
	for (int i = LG-1; i >= 0; --i)
		if (par[i][u] != par[i][v])
			u = par[i][u], v = par[i][v];
	return par[0][u];
}

vi ans;
int ed[N];
int dfs2(int v, int k, int p = -1) {
	int sm = wt[v];
	for (auto &[c, i] : G[v]) if (c != par[0][v]) sm += dfs2(c, k, i);
	if (sm >= 2*k) ans.pb(p+1);
	return sm;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, q, k, u, v;
	cin >> n >> q >> k;
	f0r(i, n-1) {
		cin >> u >> v;
		G[--u].pb({--v, i});
		G[v].pb({u, i});
	}
	dfs(0);
	int x;
	f0r(i, q) {
		cin >> x;
		vi A(x);
		forl(&a, A) cin >> a;
		sort(all(A), [](int x, int y) { return tin[x-1] < tin[y-1]; });
		A.pb(A[0]);
		f0r(i, x) {
			int u = A[i]-1, v = A[i+1]-1, l = lca(u, v);
			wt[l] -= 2, wt[u]++, wt[v]++;
		}
	}
	dfs2(0, k);
	ctn(ans.size());
	sort(all(ans));
	ctl(ans);
}

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