Submission #478073

#	Time	Username	Problem	Language	Result	Execution time	Memory
478073		Sohsoh84	Railway (BOI17_railway)	C++17	100 / 100	105 ms	26468 KiB

railway

// ?
#include <bits/stdc++.h>

using namespace std;

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

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e5 + 10;
const ll LOG = 20;

int ans[MAXN], n, m, k, par[MAXN][LOG], delta[MAXN], F[MAXN], H[MAXN], tout[MAXN], T; // tin
vector<pll> adj[MAXN];

void dfs(int v, int p) {
	H[v] = H[p] + 1;
	par[v][0] = p;
	for (pll e : adj[v])
		if (e.X != p)
			dfs(e.X, v);
	tout[v] = T++;
}

inline int Par(int v, int k) {
	for (int i = LOG - 1; i >= 0; i--)
		if (k & (1 << i))
			v = par[v][i];
	return v;
}

inline int LCA(int v, int u) {
	if (H[v] < H[u]) swap(v, u);
	v = Par(v, H[v] - H[u]);
	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 dfs2(int v, int p, int ind) {
	F[v] += delta[v];
	for (pll e : adj[v]) {
		if (e.X != p) {
			dfs2(e.X, v, e.Y);
			F[v] += F[e.X];
		}
	}

	ans[ind] = F[v] / 2;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i < n; i++) {
		int v, u;
		cin >> v >> u;
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
	}


	dfs(1, 0);
	for (int i = 1; i < LOG; i++)
		for (int v = 1; v <= n; v++)
			par[v][i] = par[par[v][i - 1]][i - 1];

	for (int i = 1; i <= m; i++) {
		int s;
		cin >> s;
		vector<int> vec;
		for (int i = 1; i <= s; i++) {
			int v;
			cin >> v;
			vec.push_back(v);
		}

		sort(all(vec), [] (int v, int u) {
			return tout[v] < tout[u];		
		});

		for (int i = 0; i < s; i++) {
			int v = vec[i], u = vec[(i + 1) % s], lca = LCA(u, v);
			delta[v]++;
			delta[u]++;
			delta[lca] -= 2;
		}
	}

	dfs2(1, 0, 0);
	vector<int> vec;
	for (int i = 1; i < n; i++)
		if (ans[i] >= k)
			vec.push_back(i);

	cout << vec.size() << endl;
	for (int e : vec) cout << e << sep;
	cout << endl;
	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