oj.uz

답안 #525334

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525334 2022-02-11T11:13:41 Z benedict0724 Firefighting (NOI20_firefighting) C++17
100 / 100
 321 ms 46368 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, ll> pi;
const ll INF = 1e18;
int n; ll k;

vector<pi> adj[300002];
bool chk[300002];
bool ou[300002];
int ans = 0;

ll dfs(int x, int p, ll d)
{
    ll ds = 0, dl = INF;
    for(auto u : adj[x])
    {
        int i = u.first;
        if(i == p) continue;
        ll c = u.second;
        ll P = dfs(i, x, c);

        if(!ou[i]) ds = max(ds, P);
        else dl = min(dl, P);
    }

    if(dl + ds > k)
    {
        if(x == 1 || d + ds > k)
        {
            chk[x] = 1; ou[x] = 1;
            ans++;
            return d;
        }
        ou[x] = 0;
        return ds + d;
    }

    if(dl + d > k) { ou[x] = 0; return 0; }
    ou[x] = 1;
    return dl + d;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> k;
    if(n == 1)
    {
        cout << "1\n1";
        return 0;
    }
    for(int i=1;i<n;i++)
    {
        int a, b; ll D; cin >> a >> b >> D;
        adj[a].push_back({b, D});
        adj[b].push_back({a, D});
    }

    ll P = dfs(1, 0, 0);

    cout << ans << "\n";

    for(int i=1;i<=n;i++) if(chk[i]) cout << i << " ";
}

Compilation message

Firefighting.cpp: In function 'int main()':
Firefighting.cpp:61:8: warning: unused variable 'P' [-Wunused-variable]
   61 |     ll P = dfs(1, 0, 0);
      |        ^

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 25856 KB Output is correct
2 Correct 268 ms 26020 KB Output is correct
3 Correct 97 ms 14192 KB Output is correct
4 Correct 285 ms 25408 KB Output is correct
5 Correct 3 ms 7372 KB Output is correct
6 Correct 4 ms 7244 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7344 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 4 ms 7324 KB Output is correct
4 Correct 4 ms 7276 KB Output is correct
5 Correct 4 ms 7316 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 5 ms 7372 KB Output is correct
8 Correct 5 ms 7244 KB Output is correct
9 Correct 4 ms 7368 KB Output is correct
10 Correct 4 ms 7368 KB Output is correct
11 Correct 4 ms 7244 KB Output is correct
12 Correct 4 ms 7372 KB Output is correct
13 Correct 4 ms 7372 KB Output is correct
14 Correct 4 ms 7368 KB Output is correct
15 Correct 6 ms 7372 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 287 ms 25932 KB Output is correct
2 Correct 144 ms 17212 KB Output is correct
3 Correct 130 ms 20316 KB Output is correct
4 Correct 141 ms 18532 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 4 ms 7244 KB Output is correct
7 Correct 231 ms 28296 KB Output is correct
8 Correct 215 ms 28172 KB Output is correct
9 Correct 208 ms 28532 KB Output is correct
10 Correct 224 ms 28288 KB Output is correct
11 Correct 321 ms 32840 KB Output is correct
12 Correct 171 ms 22608 KB Output is correct
13 Correct 81 ms 16840 KB Output is correct
14 Correct 154 ms 21916 KB Output is correct
15 Correct 188 ms 25068 KB Output is correct
16 Correct 214 ms 26256 KB Output is correct
17 Correct 164 ms 23364 KB Output is correct
18 Correct 157 ms 23028 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7500 KB Output is correct
2 Correct 4 ms 7524 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 5 ms 7628 KB Output is correct
6 Correct 6 ms 7688 KB Output is correct
7 Correct 6 ms 7628 KB Output is correct
8 Correct 5 ms 7628 KB Output is correct
9 Correct 5 ms 7576 KB Output is correct
10 Correct 5 ms 7628 KB Output is correct
11 Correct 5 ms 7620 KB Output is correct
12 Correct 5 ms 7376 KB Output is correct
13 Correct 5 ms 7628 KB Output is correct
14 Correct 6 ms 7628 KB Output is correct
15 Correct 5 ms 7572 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Correct 4 ms 7480 KB Output is correct
18 Correct 5 ms 7500 KB Output is correct
19 Correct 5 ms 7432 KB Output is correct
20 Correct 4 ms 7380 KB Output is correct
21 Correct 5 ms 7500 KB Output is correct

Subtask #6
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 246 ms 23316 KB Output is correct
2 Correct 243 ms 22348 KB Output is correct
3 Correct 243 ms 23476 KB Output is correct
4 Correct 86 ms 14896 KB Output is correct
5 Correct 287 ms 36108 KB Output is correct
6 Correct 313 ms 34636 KB Output is correct
7 Correct 261 ms 39620 KB Output is correct
8 Correct 264 ms 43408 KB Output is correct
9 Correct 289 ms 37972 KB Output is correct
10 Correct 258 ms 37060 KB Output is correct
11 Correct 293 ms 46368 KB Output is correct
12 Correct 152 ms 22928 KB Output is correct
13 Correct 287 ms 39564 KB Output is correct
14 Correct 274 ms 36264 KB Output is correct
15 Correct 274 ms 30784 KB Output is correct
16 Correct 241 ms 29252 KB Output is correct
17 Correct 234 ms 29220 KB Output is correct
18 Correct 247 ms 30784 KB Output is correct
19 Correct 161 ms 23448 KB Output is correct
20 Correct 76 ms 16372 KB Output is correct
21 Correct 239 ms 30404 KB Output is correct