oj.uz

Submission #525219

# Submission time Handle Problem Language Result Execution time Memory
525219 2022-02-11T06:25:35 Z mjhmjh1104 Firefighting (NOI20_firefighting) C++17
41 / 100
 348 ms 45200 KB 
#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);
    }
    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

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 21724 KB Output is correct
2 Correct 274 ms 21760 KB Output is correct
3 Correct 72 ms 12760 KB Output is correct
4 Correct 268 ms 21304 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 4 ms 7320 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7328 KB Output is correct
3 Correct 4 ms 7324 KB Output is correct
4 Correct 4 ms 7244 KB Output is correct
5 Incorrect 4 ms 7244 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 4 ms 7244 KB Output is correct
4 Incorrect 4 ms 7324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 21676 KB Output is correct
2 Incorrect 175 ms 14552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7328 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 7 ms 7500 KB Output is correct
6 Correct 7 ms 7524 KB Output is correct
7 Incorrect 7 ms 7588 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 18132 KB Output is correct
2 Correct 279 ms 21040 KB Output is correct
3 Correct 296 ms 21856 KB Output is correct
4 Correct 96 ms 15364 KB Output is correct
5 Correct 304 ms 38424 KB Output is correct
6 Correct 312 ms 36128 KB Output is correct
7 Correct 290 ms 43608 KB Output is correct
8 Correct 324 ms 41872 KB Output is correct
9 Correct 315 ms 33804 KB Output is correct
10 Correct 288 ms 32436 KB Output is correct
11 Correct 302 ms 45200 KB Output is correct
12 Correct 169 ms 18308 KB Output is correct
13 Correct 342 ms 35112 KB Output is correct
14 Correct 348 ms 29884 KB Output is correct
15 Correct 286 ms 22252 KB Output is correct
16 Correct 294 ms 21248 KB Output is correct
17 Correct 280 ms 21300 KB Output is correct
18 Correct 300 ms 21944 KB Output is correct
19 Correct 177 ms 18512 KB Output is correct
20 Correct 102 ms 14384 KB Output is correct
21 Correct 287 ms 22060 KB Output is correct