Submission #1285708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285708		nlsosad	Railway (BOI17_railway)	C++20	100 / 100	106 ms	36672 KiB

railway

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
int n, m, k;
vector<pair<int, int>> a[100001];
pair<int, int> e[100001];
int dem[100001];
vector<int> luu[100001];
unordered_map<int, int> mp[100001];
vector<int> res;
void dfs(int u, int p){
	for (auto [v, id]:a[u]){
		if(v!=p){
			dfs(v, u);
			if(mp[v].size()>=k){
				res.push_back(id);
			}
			if(mp[u].size() < mp[v].size())swap(mp[u], mp[v]);
			for (auto i:mp[v]){
				mp[u][i.f]+=i.s;
				if(mp[u][i.f]==dem[i.f])mp[u].erase(i.f);
			}
		}
	}
	for (int i:luu[u]){
		mp[u][i]++;
		if(mp[u][i]==dem[i])mp[u].erase(i);
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k;
	for (int i= 1;i<n;++i){
		int u, v;
		cin >> u >> v;
		a[u].push_back({v, i});
		a[v].push_back({u, i});
	}
	for (int i = 1;i<=m;++i){
		int s;
		cin >> s;
		dem[i] = s;
		for (int j = 1;j<=s;++j){
			int u;
			cin >> u;
			luu[u].push_back(i);
		}
	}
	dfs(1, 0);
	sort(res.begin(), res.end());
	cout << res.size() << '\n';
	for (int i:res){
		cout << i << ' ';
	}
}

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