Submission #525224

#	Time	Username	Problem	Language	Result	Execution time	Memory
525224		mjhmjh1104	Firefighting (NOI20_firefighting)	C++17	100 / 100	340 ms	42044 KiB

Firefighting

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int n;
long long k;
vector<pair<int, int>> adj[300006];
vector<int> res;

pair<long long, bool> dfs(int x, int prev = -1) {
    long long rev = 0;
    bool fine = false;
    vector<long long> v;
    for (auto &i: adj[x]) if (i.first != prev) {
        pair<long long, bool> p = dfs(i.first, x);
        long long t = p.first + i.second;
        if (!p.second && t > k) {
            res.push_back(i.first);
            t = i.second - k;
            p.second = true;
        }
        if (t < 0) rev = max(rev, -t), fine = true;
        else if (!p.second) v.push_back(t);
        else if (!t) fine = true;
    }
    sort(v.rbegin(), v.rend());
    if (v.empty()) return { -rev, fine };
    if (v[0] <= rev) return { -rev, true };
    if (v[0] >= k) {
        res.push_back(x);
        return { -k, true };
    }
    return { v[0], false };
}

int main() {
    scanf("%d%lld", &n, &k);
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        a--, b--;
        adj[a].push_back({ b, c });
        adj[b].push_back({ a, c });
    }
    if (n == 1) {
        puts("1\n1");
        return 0;
    }
    if (n == 2) {
        if (adj[0][0].second <= k) puts("1\n1");
        else puts("2\n1 2");
        return 0;
    }
    if (!dfs(0).second) res.push_back(0);
    printf("%d\n", (int)res.size());
    for (auto &i: res) printf("%d ", i + 1);
}

Compilation message (stderr)

Firefighting.cpp: In function 'int main()':
Firefighting.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d%lld", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
Firefighting.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%d%d%d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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