Submission #830212

#	Time	Username	Problem	Language	Result	Execution time	Memory
830212		NK_	Firefighting (NOI20_firefighting)	C++17	72 / 100	252 ms	51044 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;

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; vi G(N);
	function<ll(int, int, int)> dfs = [&](int u, int p, int d) {
		vpl chd; for(auto& e : adj[u]) {
			auto [v, w] = e; if (v == p) continue;
			ll f = dfs(v, u, w) + w; 
			if (f > 0 && G[v]) f = 0, G[v] = 0;
			chd.pb(mp(f, v));
		}

		sort(begin(chd), end(chd), [&](auto a, auto b) {
			if (a.f == b.f) return G[a.s] < G[b.s];
			return a.f < b.f;
		});

		// cout << u << endl;
		// for(auto x : chd) {
		// 	cout << x.f << " " << x.s << " " << G[x.s] << endl;
		// }
		// cout << endl;

		if (sz(chd) == 0) {
			if (d > K) {
				ans.pb(u);
				G[u] = 1; return -K;
			} else return 0LL;
		}

		bool good = (chd.front().f + chd.back().f) <= 0;
		if (good) { // good subtree (take front)
			G[u] = G[chd.front().s]; 
			ll far = chd.front().f;
			if (!G[u] && (far + d) > K) {
				ans.pb(u); G[u] = 1; return -K; 
			} else return far;
		} else { // bad subtree (take back)
			ll far = chd.back().f;
			if ((far + d) > K) {
				ans.pb(u);
				G[u] = 1; return -K;
			} else return far;
		}
	};



	ll far = dfs(0, -1, 0);
	if (far >= 0 && !G[0]) ans.pb(0); 

	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: 0 / 9
• Subtask 4: 0 / 19
• Subtask 5: 26 / 26
• Subtask 6: 38 / 38