Submission #1170248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170248		susanthenerd	Firefighting (NOI20_firefighting)	C++20	100 / 100	131 ms	36800 KiB

Firefighting

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, k;
    cin >> n >> k;


    vector<vector<pair<ll, ll> > > adj(n + 1);

    for (ll i = 1; i < n; ++i) {
        ll u, v, c;
        cin >> u >> v >> c;
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, c);
    }


    vector<ll> ans;
    auto dfs = [&](auto &&self, ll u, ll p, ll cur) -> pair<bool, ll> {
        ll acoperit = -1e15, neacoperit = 0;
        for (auto &[v, c]: adj[u]) {
            if (v == p) continue;


            if (auto t = self(self, v, u, c); t.first) {
                acoperit = max(acoperit, t.second);
            } else {
                neacoperit = max(neacoperit, t.second);
            }
        }


        pair<bool, ll> nod;

        if (acoperit >= neacoperit) {
            nod = {true, acoperit - cur};
        } else {
            nod = {false, neacoperit + cur};
        }

        if (!nod.first && nod.second > k) {
            ans.push_back(u);
            nod = {true, k - cur};
        }

        if (nod.first && nod.second < 0)
            nod = {false, 0};

        return nod;
    };

    dfs(dfs, 1, 0, 1e15);
    cout << ans.size() << '\n';
    for (const auto &it: ans)
        cout << it << ' ';
    cout << '\n';
}

/*
9 4
1 2 10
2 3 4
8 9 4
8 7 3
7 3 5
3 4 1
4 5 3
5 6 2
*/

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