Submission #568296

#	Time	Username	Problem	Language	Result	Execution time	Memory
568296		_karan_gandhi	Railway (BOI17_railway)	C++17	100 / 100	450 ms	38928 KiB

railway

#include <bits/stdc++.h>
using namespace std;

#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
#define ll long long

vector<vector<pair<int, int>>> adj;
multiset<int> token[100'010];
vector<int> s;
int k;
vector<int> ans;
vector<int> votes;

void merge(int u, int v) {
	if (token[u].size() < token[v].size()) {
		swap(token[u], token[v]);
		swap(votes[u], votes[v]);
	}

	for (int elt : token[v]) {
		token[u].insert(elt);
		int cnt = token[u].count(elt);

		if (cnt == s[elt]) {
			votes[u]--;
		} else if (cnt == 1) {
			votes[u]++;
		}
	}
}

void dfs(int u, int par, int idx) {
	for (auto [v, _idx] : adj[u]) {
		if (v == par) continue;
		dfs(v, u, _idx);
	}

	if (idx == -1) return;

	for (auto [v, _] : adj[u]) {
		if (v == par) continue;

		merge(u, v);
	}

	if (votes[u] >= k) {
		ans.push_back(idx);
	}
}

void solve() {
	int n, m; cin >> n >> m >> k;

	adj.resize(n);
	votes.resize(n); // number of votes for the ith edge
	s.resize(m);

	for (int i = 0; i < n - 1; i++) {
		int a, b; cin >> a >> b;
		a--, b--;
		adj[a].emplace_back(b, i);
		adj[b].emplace_back(a, i);
	}

	for (int i = 0; i < m; i++) {
		cin >> s[i];
		assert(s[i] >= 1);
		for (int j = 0; j < s[i]; j++) {
			int a; cin >> a;
			token[a - 1].insert(i);
			votes[a - 1]++;
		}
	}

	dfs(0, 0, -1);

	cout << ans.size() << endl;
	sort(all(ans));
	for (int i : ans) cout << i+1 << ' ';
	cout << endl;
}

int main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	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