Submission #697198

#	Time	Username	Problem	Language	Result	Execution time	Memory
697198		MISM06	Railway (BOI17_railway)	C++14	100 / 100	167 ms	28508 KiB

railway

//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
//uoy kcuf;
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")

using namespace std;

#define F 			first
#define S 			second
#define pb 			push_back
#define sze			size()
#define	all(x)		x.begin() , x.end()
#define wall__		cout << "--------------------------------------\n";
#define node		int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io		freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);

typedef long long ll;
typedef long double dl;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;


const ll N = 2e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 2e16;
const ll rinf = -2e16;
const ll INF = 1e9 + 10;
const ll rINF = -1e9 - 10;
const ll lg = 20;

int m, k, st[N], en[N], timer = 0, par[lg][N], a[N], id[N];
vector < pii > g[N];
void dfs (int v, int p) {
	st[v] = ++timer;
	par[0][v] = p; for (int i = 1; i < lg; i++) par[i][v] = par[i - 1][par[i - 1][v]];
	for (auto u : g[v]) if (u.F != p) {
		dfs(u.F, v);
		id[u.S] = u.F;
	}
	en[v] = timer;
}
bool be_anc (int v, int u) {
	return st[v] <= st[u] && en[v] >= en[u];
}
int LCA (int v, int u) {
	if (be_anc(v, u)) return v;
	if (be_anc(u, v)) return u;
	for (int i = lg - 1; i >= 0; --i) if (!be_anc(par[i][v], u)) v = par[i][v];
	return par[0][v];
}
void calc (int n) {
	vector < pii > ver;
	int lca = -1;
	for (int i = 1; i <= n; i++) {
		int v; cin >> v;
		if (lca == -1) lca = v;
		lca = LCA(lca, v);
		ver.pb({st[v], v});
	} ver.pb({st[lca], lca}); sort(all(ver));
	for (int i = 1; i <= n; i++) {
		int v = ver[i].S, u = ver[i - 1].S;
		--a[LCA(v, u)]; ++a[v];
	}
}
void make (int v, int p) {
	for (auto u : g[v]) {
		if (u.F == p) continue;
		make(u.F, v);
		a[v] += a[u.F];
	}
}
void solve () {

	int n;
	cin >> n >> m >> k; st[0] = -1; en[0] = INF;
	for (int i = 1; i < n; i++) {
		int v, u; cin >> v >> u;
		g[v].pb({u, i});
		g[u].pb({v, i});
	}
	dfs(1, 0);
	for (int i = 1; i <= m; i++) {
		int s; cin >> s; calc(s);
	}
	make(1, 0);
	vector < int > ord;
	for (int i = 1; i < n; i++) {
		if (a[id[i]] >= k) ord.pb(i);
	}
	cout << ord.sze << '\n';
	for (auto x : ord) cout << x << " ";

}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	
	int t = 1;
	// cin >> t;
	while (t--) {solve();}

    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