oj.uz

답안 #525229

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525229 2022-02-11T07:13:05 Z mjhmjh1104 Firefighting (NOI20_firefighting) C++17
64 / 100
 329 ms 42680 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);
        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 1;
    }
    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: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
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 267 ms 21732 KB Output is correct
2 Correct 307 ms 21656 KB Output is correct
3 Correct 101 ms 12752 KB Output is correct
4 Correct 252 ms 21304 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Runtime error 4 ms 7244 KB Execution failed because the return code was nonzero
7 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7268 KB Output is correct
3 Runtime error 4 ms 7244 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 4 ms 7328 KB Output is correct
4 Correct 4 ms 7328 KB Output is correct
5 Correct 4 ms 7304 KB Output is correct
6 Correct 4 ms 7328 KB Output is correct
7 Correct 4 ms 7244 KB Output is correct
8 Runtime error 4 ms 7244 KB Execution failed because the return code was nonzero
9 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 262 ms 21688 KB Output is correct
2 Correct 115 ms 14536 KB Output is correct
3 Correct 131 ms 15388 KB Output is correct
4 Correct 117 ms 14368 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Runtime error 4 ms 7324 KB Execution failed because the return code was nonzero
7 Halted 0 ms 0 KB -

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7316 KB Output is correct
4 Correct 5 ms 7396 KB Output is correct
5 Correct 5 ms 7584 KB Output is correct
6 Correct 5 ms 7628 KB Output is correct
7 Correct 6 ms 7628 KB Output is correct
8 Correct 6 ms 7596 KB Output is correct
9 Correct 5 ms 7492 KB Output is correct
10 Correct 5 ms 7588 KB Output is correct
11 Correct 7 ms 7604 KB Output is correct
12 Correct 4 ms 7376 KB Output is correct
13 Correct 5 ms 7628 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 6 ms 7500 KB Output is correct
16 Correct 5 ms 7372 KB Output is correct
17 Correct 5 ms 7348 KB Output is correct
18 Correct 5 ms 7468 KB Output is correct
19 Correct 5 ms 7360 KB Output is correct
20 Correct 7 ms 7332 KB Output is correct
21 Correct 5 ms 7460 KB Output is correct

Subtask #6
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 245 ms 18120 KB Output is correct
2 Correct 244 ms 18628 KB Output is correct
3 Correct 279 ms 19492 KB Output is correct
4 Correct 100 ms 13108 KB Output is correct
5 Correct 295 ms 36032 KB Output is correct
6 Correct 294 ms 33720 KB Output is correct
7 Correct 329 ms 41024 KB Output is correct
8 Correct 293 ms 39708 KB Output is correct
9 Correct 291 ms 31384 KB Output is correct
10 Correct 287 ms 30132 KB Output is correct
11 Correct 305 ms 42680 KB Output is correct
12 Correct 169 ms 15916 KB Output is correct
13 Correct 287 ms 32504 KB Output is correct
14 Correct 287 ms 27448 KB Output is correct
15 Correct 261 ms 19652 KB Output is correct
16 Correct 242 ms 18812 KB Output is correct
17 Correct 254 ms 19024 KB Output is correct
18 Correct 269 ms 19516 KB Output is correct
19 Correct 185 ms 16184 KB Output is correct
20 Correct 79 ms 12356 KB Output is correct
21 Correct 266 ms 19588 KB Output is correct