제출 #1170248

#제출 시각아이디문제언어결과실행 시간메모리
1170248susanthenerdFirefighting (NOI20_firefighting)C++20
100 / 100
131 ms36800 KiB
#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
*/
#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...