제출 #1280744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280744		nanaseyuzuki	Railway (BOI17_railway)	C++20	100 / 100	120 ms	50428 KiB

railway

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 2e5 + 5, B = 450, nB = 3005, lg2 = 20, mbit = (1 << 20) + 1, mm = 5e3 + 5, mod = 1e6 + 3, inf = 1e18;

int n, m, k, st[mn], ft[mn], up[mn][20], id[mn], d[mn], timer = 0, dp[mn];
vector <pii> a[mn];

void pre_dfs(int u, int p){
	st[u] = ++ timer;
	for(auto [v, i] : a[u]){
		if(v == p) continue;
		id[v] = i;
		up[v][0] = u;
		d[v] = d[u] + 1;
		for(int i = 1; i <= 16; i++){
			if(up[v][i - 1] != -1) up[v][i] = up[up[v][i - 1]][i - 1];
		}
		pre_dfs(v, u);
	}
	ft[u] = timer;
}

int lca(int u, int v){
	if(d[u] < d[v]) swap(u, v);
	int kc = d[u] - d[v];
	for(int i = 16; i >= 0; i--){
		if(kc & (1 << i)) u = up[u][i];
	}
	if(u == v) return u;
	for(int i = 16; i >= 0; i--){
		if(up[u][i] != -1 && up[v][i] != -1 && up[u][i] != up[v][i]){
			u = up[u][i];
			v = up[v][i];
		}
	}
	return up[u][0];
}

bool cmp(int u, int v){
	return st[u] < st[v];
}

void dfs2(int u, int p){
	for(auto [v, i] : a[u]){
		if(v == p) continue;
		dfs2(v, u);
		dp[u] += dp[v];
	}
}

void solve(){
    cin >> n >> m >> k;
	for(int i = 1; i < n; i++){
		int u, v; cin >> u >> v;
		a[u].push_back({v, i});
		a[v].push_back({u, i});
	}
	memset(up, -1, sizeof(up));
	pre_dfs(1, 0);
	for(int i = 1; i <= m; i++){
		int s; cin >> s;
		vector <int> pts;
		for(int i = 1; i <= s; i++){
			int u; cin >> u;
			pts.push_back(u);
		}
		sort(all(pts), cmp);
		pts.push_back(pts[0]);
		for(int j = 0; j < s; j++){
			int u = pts[j], v = pts[j + 1];
			// cout << u << ' ' << v << ' ' << lca(u, v) << '\n';
			dp[u] ++, dp[v] ++, dp[lca(u, v)] -= 2;
		}
	}
	// cout << dp[4] << ' ' << dp[5] << ' ' << dp[6] << '\n';
	dfs2(1, 0);
	vector <int> ans;
	for(int i = 2; i <= n; i++){
		if(dp[i] >= 2 * k) ans.push_back(id[i]);
	}
	sort(all(ans));
	cout << ans.size() << '\n';
	for(auto i : ans) cout << i << ' ';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

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