Submission #830222

#	Time	Username	Problem	Language	Result	Execution time	Memory
830222		NK_	Firefighting (NOI20_firefighting)	C++17	36 / 100	241 ms	28476 KiB

Firefighting

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;
 
#define nl '\n'
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;

using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;

using db = long double;

const int MOD = 1e9 + 7;
const ll INFL = ll(1e16) + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; ll K; cin >> N >> K;

	V<vpi> adj(N); for(int i = 0; i < N-1; i++) {
		int u, v, w; cin >> u >> v >> w; --u, --v;
		adj[u].pb(mp(v, w));
		adj[v].pb(mp(u, w));
	}


	vi ans;
	function<pl(int, int, ll)> dfs = [&](int u, int p, ll d) {
		ll close = -INFL, far = 0;
		for(auto& e : adj[u]) {
			auto [v, w] = e; if (v == p) continue;
			pl R = dfs(v, u, w);
			if (R.f) {
				close = max(close, R.s);
			} else {
				far = max(far, R.s);
			}
		}

		pl R;
		if (close >= far) {
			R = mp(1, close - d);
		} else {
			R = mp(0, far + d);
		}

		if (R.f && R.s < 0) R = mp(0, 0);
		
		if (!R.f && R.s > K) {
			ans.pb(u); R = mp(1, K - d);
		}
		return R;
	};


	dfs(0, -1, MOD);

	cout << sz(ans) << nl;
	for(auto& x : ans) cout << x + 1 << " ";
	cout << nl;

    return 0;
} 

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