oj.uz

답안 #959539

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
959539 2024-04-08T12:16:53 Z Blagoj Firefighting (NOI20_firefighting) C++17
100 / 100
 246 ms 44172 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 3e5 + 10;

ll n, k;

vector<pair<ll, ll>> g[mxn];
vector<int> ans;

pair<bool, ll> dfs(int cur, int par = -1, ll dist = 1e16) {
    ll mxOver = -1e16, mxUnder = 0;
    for (auto [to, weight] : g[cur]) {
        if (to == par) continue;
        auto res = dfs(to, cur, weight);
        if (res.first) mxOver = max(mxOver, res.second);
        else mxUnder = max(mxUnder, res.second);
    }
    pair<bool, ll> res;
    if (mxOver >= mxUnder) res = {1, mxOver - dist};
    else res = {0, mxUnder + dist};
    if (!res.first && res.second > k) {
        res = {1, k - dist};
        ans.push_back(cur);
    }
    if (res.first && res.second < 0) res = {0, 0};
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
        ll f, t, w;
        cin >> f >> t >> w;
        g[f].push_back({t, w});
        g[t].push_back({f, w});
    }
    dfs(1);
    cout << ans.size() << endl;
    for (auto x : ans) cout << x << " ";
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 198 ms 33488 KB Output is correct
2 Correct 200 ms 33388 KB Output is correct
3 Correct 62 ms 16920 KB Output is correct
4 Correct 204 ms 32920 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 3 ms 7260 KB Output is correct
11 Correct 2 ms 7268 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct
13 Correct 2 ms 7260 KB Output is correct
14 Correct 2 ms 7260 KB Output is correct
15 Correct 2 ms 7260 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7760 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7256 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 2 ms 7260 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct
13 Correct 2 ms 7260 KB Output is correct
14 Correct 2 ms 7260 KB Output is correct
15 Correct 2 ms 7260 KB Output is correct
16 Correct 3 ms 7260 KB Output is correct
17 Correct 2 ms 7260 KB Output is correct
18 Correct 2 ms 7260 KB Output is correct
19 Correct 2 ms 7260 KB Output is correct
20 Correct 2 ms 7260 KB Output is correct
21 Correct 2 ms 7260 KB Output is correct
22 Correct 2 ms 7260 KB Output is correct
23 Correct 2 ms 7260 KB Output is correct
24 Correct 2 ms 7260 KB Output is correct
25 Correct 3 ms 7504 KB Output is correct
26 Correct 2 ms 7260 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 33416 KB Output is correct
2 Correct 88 ms 19920 KB Output is correct
3 Correct 133 ms 20424 KB Output is correct
4 Correct 68 ms 18636 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 150 ms 30080 KB Output is correct
8 Correct 133 ms 29724 KB Output is correct
9 Correct 133 ms 30644 KB Output is correct
10 Correct 202 ms 31160 KB Output is correct
11 Correct 213 ms 33580 KB Output is correct
12 Correct 120 ms 23148 KB Output is correct
13 Correct 59 ms 17096 KB Output is correct
14 Correct 102 ms 22188 KB Output is correct
15 Correct 130 ms 25520 KB Output is correct
16 Correct 144 ms 26484 KB Output is correct
17 Correct 156 ms 23396 KB Output is correct
18 Correct 107 ms 23176 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 4 ms 7512 KB Output is correct
3 Correct 3 ms 7512 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7772 KB Output is correct
6 Correct 3 ms 7772 KB Output is correct
7 Correct 3 ms 7772 KB Output is correct
8 Correct 3 ms 7772 KB Output is correct
9 Correct 3 ms 7772 KB Output is correct
10 Correct 4 ms 7772 KB Output is correct
11 Correct 3 ms 8024 KB Output is correct
12 Correct 3 ms 7512 KB Output is correct
13 Correct 3 ms 7772 KB Output is correct
14 Correct 3 ms 7772 KB Output is correct
15 Correct 3 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 3 ms 7516 KB Output is correct
19 Correct 3 ms 7516 KB Output is correct
20 Correct 3 ms 7516 KB Output is correct
21 Correct 4 ms 7516 KB Output is correct

Subtask #6
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 29664 KB Output is correct
2 Correct 153 ms 28456 KB Output is correct
3 Correct 208 ms 29988 KB Output is correct
4 Correct 71 ms 17748 KB Output is correct
5 Correct 191 ms 39740 KB Output is correct
6 Correct 241 ms 38596 KB Output is correct
7 Correct 232 ms 42224 KB Output is correct
8 Correct 183 ms 41312 KB Output is correct
9 Correct 216 ms 36556 KB Output is correct
10 Correct 226 ms 35680 KB Output is correct
11 Correct 188 ms 44172 KB Output is correct
12 Correct 95 ms 22664 KB Output is correct
13 Correct 201 ms 38136 KB Output is correct
14 Correct 178 ms 35280 KB Output is correct
15 Correct 198 ms 30332 KB Output is correct
16 Correct 170 ms 28900 KB Output is correct
17 Correct 166 ms 28564 KB Output is correct
18 Correct 246 ms 30040 KB Output is correct
19 Correct 127 ms 23292 KB Output is correct
20 Correct 44 ms 16464 KB Output is correct
21 Correct 170 ms 30516 KB Output is correct