Submission #333227

#TimeUsernameProblemLanguageResultExecution timeMemory
333227CantfindmeFirefighting (NOI20_firefighting)C++17
100 / 100
367 ms44892 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
const int maxn = 300010;
const int INF = LLONG_MAX/3;

int n,k;
vector <pi> adjlist[maxn];
vector <int> ans;

int dfs(int x, int p, int d) {
	int maxover = -INF, minunder = 0;
	for (auto i: adjlist[x]) if (i.f != p) {
		int res = dfs(i.f,x,i.s);
		if (res < 0) minunder = min(minunder,res);
		else if (res > 0) maxover = max(maxover,res - i.s);
	}
	
	int res = 0;
	if (maxover < abs(minunder)) { 
		if (abs(minunder) + d <= k) { //delay. Underflow
			res = -(abs(minunder) + d);
		} else { //Build here. overflow.
			ans.push_back(x);
			res = k;
		}
	} else if (maxover >= abs(minunder)) {
		res = maxover;
	}
	return res;
}

int32_t main() {
	FAST	
	cin >> n >> k;
	for (int i =0;i<n-1;i++) {
		int a,b,d; cin >> a >> b >> d;
		adjlist[a].push_back(pi(b,d));
		adjlist[b].push_back(pi(a,d));
	}
	
	dfs(1,-1,INF);
	cout << ans.size() << "\n";
	for (auto i: ans) 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...