Submission #333227

#	Time	Username	Problem	Language	Result	Execution time	Memory
333227		Cantfindme	Firefighting (NOI20_firefighting)	C++17	100 / 100	367 ms	44892 KiB

Firefighting

#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 << " ";
	
}

• Subtask 1: 3 / 3
• Subtask 2: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26
• Subtask 6: 38 / 38