Submission #1279261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279261		g4yuhg	Railway (BOI17_railway)	C++20	100 / 100	166 ms	25836 KiB

railway

//Huyduocdithitp
#include<bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll,ll>
#define N 100005
#define LOG 18
using namespace std;

bool ghuy4g;

ll n, m, k;
ll high[N], sz[N], chain_head[N], chain_id[N], cur_pos, cur_chain, in[N], out[N], timeDfs, par[N], pos[N];
pii canh[N];

vector<ll> adj[N];

ll lca(ll u, ll v) {
	while (chain_id[u] != chain_id[v]) {
		if (chain_id[u] > chain_id[v]){
			u = par[chain_head[chain_id[u]]];
		}
		else {
			v = par[chain_head[chain_id[v]]];
		}
	}
	if (high[u] > high[v]) return v;
	else return u;
}

ll is_anc(ll u, ll v) {
	return (in[u] <= in[v] && in[v] <= out[u]);
}

void dfs(ll u, ll parent) {
	in[u] = ++timeDfs;
	sz[u] = 1;
	for (auto v : adj[u]) {
		if (v == parent) continue;
		high[v] = high[u] + 1;
		dfs(v, u);
		par[v] = u;
		sz[u] += sz[v];
	}
	out[u] = timeDfs;
}
 
void hld(ll u, ll parent) {
	if (chain_head[cur_chain] == 0) {
		chain_head[cur_chain] = u;
	}
	chain_id[u] = cur_chain;
	pos[u] = cur_pos;
	cur_pos ++ ;
	ll nxt = 0;
	for (auto v : adj[u]) {
		if (v == parent) continue;
		if (sz[v] > sz[nxt]) {
			nxt = v;
		}
	}
	if (nxt) {
		hld(nxt, u);
	}
	for (auto v : adj[u]) {
		if (v == parent || v == nxt) continue;
		cur_chain ++ ;
		hld(v, u);
	}
}

ll f[4 * N], st[4 * N];

void lazy(ll id) {
	if (f[id] == 0) return;
	st[id] += f[id];
	if (id * 2 < 4 * N) {
		f[id * 2] += f[id];
	}
	if (id * 2 + 1 < 4 * N) {
		f[id * 2 + 1] += f[id];
	}
	f[id] = 0;
}

void update(ll id, ll l, ll r, ll L, ll R, ll v) {
	lazy(id);
	if (l > R || r < L) return;
	if (L <= l && r <= R) {
		f[id] += v;
		lazy(id);
		return;
	}
	ll mid = (l + r) / 2;
	update(id * 2, l, mid, L, R, v);
	update(id * 2 + 1, mid + 1, r, L, R, v);
	st[id] = st[id * 2] + st[id * 2 + 1];
}

void upd(ll u, ll v, ll tt) {
	while (chain_id[u] != chain_id[v]) {
		ll r = chain_head[chain_id[u]];
		update(1, 1, n, pos[r], pos[u], 1);
		u = par[r];
	}
	update(1, 1, n, pos[v] + 1, pos[u], 1);
}

ll cnt = 0;

ll get(ll id, ll l, ll r, ll i) {
	//return 0;
	////cout << id << " " << l << " " << r << " " << i << endl; 
	//exit(0);
	lazy(id);
	if (i > r || i < l) return 0;
	if (l == r) return st[id];
	ll mid = (l + r) / 2;
	return get(id * 2, l, mid, i) + get(id * 2 + 1, mid + 1, r, i);
}

void pre() {
	dfs(1, 1);
	cur_pos = cur_chain = 1;
	hld(1, 1);
}

bool cmp(ll u, ll v) {
	return in[u] < in[v];
}

stack<ll> St;

void xly() {
	ll k;
	vector<ll> vt;
	cin >> k;
	ll lc = 0;
	for (int i = 1; i <= k; i ++) {
		ll u; cin >> u;
		vt.push_back(u);
		if (lc == 0) lc = u;
		else {
			lc = lca(u, lc);
		}
	}
	sort(vt.begin(), vt.end(), cmp);
	for (auto it : vt) {
		//cout << it << " ";
	}
	//cout << endl;
	upd(vt[0], lc, 1);
	//cout << " upd " << vt[0] << " " << lc << endl;
	for (int i = 1; i < k; i ++) {
		ll x = lca(vt[i], vt[i - 1]);
		upd(vt[i], x, 1);
		//cout << " upd " << vt[i] << " " << x << endl; 
	}
}

void solve() {
	for (int i = 1; i <= m; i ++) {
		xly();
	}
	//return;
	vector<ll> res;
	for (int i = 1; i <= n - 1; i ++) {
		ll u = canh[i].fi, v = canh[i].se;
		if (u == par[v]) swap(u, v);
		//cout << u << " " << pos[u] << endl;
		//continue;
		ll x = get(1, 1, n, pos[u]);
		//continue;
		//cout << x << endl;
		if (x >= k) {
			res.push_back(i);
		}
	}
	//return;
	cout << res.size() << endl;
	for (auto it : res) {
		cout << it << " ";
	}
}

bool klinh;

signed main() {
	//freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> k;
	for (int i = 1; i <= n - 1; i ++) {
		ll u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		canh[i] = {u, v};
	}
	
	pre();
	
	solve();
		
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
	
	return 0;
}

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