Submission #1308981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308981		pasta	Railway (BOI17_railway)	C++20	36 / 100	67 ms	36280 KiB

railway

//Oh? You're Approaching Me?

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

#define int long long

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;


// #pragma GCC optimize("O3,unroll-loops")
#define migmig     			ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          		push_back
#define F           		first
#define S           		second
#define SZ(x)       		ll((x).size())
#define all(x)      		(x).begin(), (x).end()
#define cl          		clear
#define endl        		'\n'
#define deb(x)    			cerr << #x << " = " << x << '\n'
#define dokme(x)			{cout << x << endl; return;}
#define wtf					cout << "[ahaaaaaaaaaaaaaaaa]" << endl;

const int maxn = 2e5 + 21;
const int mod = 998244353;
const int inf = 1e18;
const int LOG = 23;
const int sq = 300;
//g++ main.cpp -o main && main.exe
//#define lc  (id * 2)
//#define rc  (lc + 1)
//#define mid ((l + r) / 2)

int n, m, k, st[maxn], fn[maxn], ps[maxn], par[maxn][LOG], h[maxn], timer = 0;
vector<pii> G[maxn];

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


int get_par(int v, int d) {
	int res = v;
	for (int i = 0; i < LOG; i++) {
		if ((d >> i) & 1)
			res = par[res][i];
	}
	return res;
}

int LCA(int v, int u) {
	if (h[v] > h[u])
		swap(v, u);
	u = get_par(u, h[u] - h[v]);
	if (v == u)
		return v;
	for (int i = LOG - 1; i >= 0; i--) {
		if (par[v][i] != par[u][i]) {
			v = par[v][i];
			u = par[u][i];
		}
	}
	return par[v][0];
}

void update(int v, int u) {
	ps[v]++;
	ps[u]++;
	ps[LCA(v, u)] -= 2;
	return;
}

vector<int> ret;
void dfs(int v, int p, int id = 0) {
	for (auto [u, i] : G[v]) {
		if (u != p) {
			dfs(u, v, i);
			ps[v] += ps[u];
		}
	}
	if (id && ps[v] >= k) {
		ret.pb(id);
	}
}
signed main() {
	migmig;
	cin >> n >> m >> k;
	for (int i = 1; i < n; i++) {
		int v, u;
		cin >> v >> u;
		G[v].pb({u, i});
		G[u].pb({v, i});
	}
	pre_dfs(1, 0);
	for (int i = 1; i <= m; i++) {
		int s; cin >> s;
		vector<pii> vc;
		for (int i = 1; i <= s; i++) {
			int x; cin >> x;
			vc.pb({st[x], x});
		}
		sort(all(vc));
		for (int i = 0; i < s - 1; i++) {
			update(vc[i].S, vc[i + 1].S);
		}
	}
	dfs(1, 0);
	sort(all(ret));
	cout << SZ(ret) << '\n';
	for (int x : ret) {
		cout << x << ' ';
	}
	cout << '\n';
}

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