Submission #395458

#	Time	Username	Problem	Language	Result	Execution time	Memory
395458		Nordway	Railway (BOI17_railway)	C++17	100 / 100	197 ms	25228 KiB

railway

#include <bits/stdc++.h>


using namespace std;

const int N = 1e5 + 1;

vector <pair<int, int>> g[N];
int timer, tin[N], tout[N], up[N][18];

void dfs(int v, int p = 1) {
	tin[v] = ++timer;
	up[v][0] = p;
	for (int i = 1; i <= 17; i++) up[v][i] = up[up[v][i - 1]][i - 1];
	for (pair<int, int> to : g[v]) {
		if (to.first != p) {
			dfs(to.first, v);
		}
	}
	tout[v] = timer;
}

bool upper(int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
	if (upper(u, v)) return u;
	if (upper(v, u)) return v;
	for (int i = 17; i >= 0; i--) {
		if (!upper(up[u][i], v)) {
			u = up[u][i];
		}
	}
	return up[u][0];
}

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

int cnt[N], dp[N];

void dfs2(int v, int p = 1, int edg = 0) {
	for (pair<int, int> to : g[v]) {
		if (to.first != p) {
			dfs2(to.first, v, to.second);
			dp[v] += dp[to.first];
		}
	}
	cnt[edg] = dp[v];
}

int main(){

	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(make_pair(v, i));
		g[v].push_back(make_pair(u, i));
	}
	dfs(1);
	for (int i = 1; i <= m; i++) {
		int s;
		cin >> s;
		vector <int> S;
		for (int j = 1; j <= s; j++) {
			int a;
			cin >> a;
			S.push_back(a);
		}
		sort(S.begin(), S.end(), cmp);
		for (int j = 0; j < s; j++) {
			int u = S[j], v = S[(j + 1) % s];
			int L = lca(u, v);
			dp[u]++, dp[v]++;
			dp[L] -= 2;
		}
	}
	dfs2(1);
	vector <int> ans;
	for (int i = 1; i < n; i++) {
		if (cnt[i] >= k + k) {
			ans.push_back(i);
		}
	}
	cout << ans.size() << "\n";
	for (int edg : ans) cout << edg << " ";
}

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