제출 #1285708

#제출 시각아이디문제언어결과실행 시간메모리
1285708nlsosadRailway (BOI17_railway)C++20
100 / 100
106 ms36672 KiB
#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 << ' ';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...