Submission #171276

#	Time	Username	Problem	Language	Result	Execution time	Memory
171276		ruler	Railway (BOI17_railway)	C++14	100 / 100	347 ms	33940 KiB

railway

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

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

////////////////////////////////////////////////////////////////////

const int N = 1e5 + 5;

int k, SZ[N], S[N], C[N];
vector<int> M[N];
vector<pii> G[N];
vector<int> E;

int DFSZ(int v, int p = 0) {
	SZ[v] = 1;
	for (pii e : G[v]) if (e.second != p) SZ[v] += DFSZ(e.first, e.second);
	return SZ[v];
}
void DFS(int v, int p, map<int, int> &mp) {
	pii bigE = make_pair(0, 0);
	for (pii e : G[v]) if (e.second != p && SZ[e.first] > SZ[bigE.first]) bigE = e;
	if (bigE.first) DFS(bigE.first, bigE.second, mp), C[v] = C[bigE.first];
	map<int, int> tmp;
	for (pii e : G[v]) if (e.second != p && e != bigE) {
		DFS(e.first, e.second, tmp);
		for (pii m : tmp) {
			mp[m.first] += m.second;
			if (mp[m.first] == S[m.first]) C[v]++;
		}
		tmp.clear();
	}
	for (int m : M[v]) if (++mp[m] == S[m]) C[v]++;
	if (k <= sz(mp) - C[v]) E.push_back(p);
}

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n, m; cin >> n >> m >> k;
	for (int i = 1; i < n; i++) {
		int v, u; cin >> v >> u;
		G[v].push_back(make_pair(u, i));
		G[u].push_back(make_pair(v, i));
	}
	DFSZ(1);
	for (int i = 1; i <= m; i++) {
		cin >> S[i];
		for (int j = 1; j <= S[i]; j++) {
			int v; cin >> v;
			M[v].push_back(i);
		}
	}
	map<int, int> tmp;
	DFS(1, 0, tmp);
	sort(all(E));
	cout << sz(E) << endl;
	for (int e : E) cout << e << ends;
	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