oj.uz

Submission #682564

# Submission time Handle Problem Language Result Execution time Memory
682564 2023-01-16T14:11:09 Z raysh07 Firefighting (NOI20_firefighting) C++17
100 / 100
 300 ms 47456 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e5 + 69;
vector<pair<int, int>> adj[maxn];
bool type[maxn];
vector<int> ans;
int n, k;

int dfs(int c, int p, int len) 
{
    int ma = 0, mi = INF;
    for(auto n2 : adj[c]) {
        int n = n2.first;
        int d = n2.second;
        if(n==p) continue;
        int l = dfs(n, c, d);
        
        if(type[n]) mi = min(mi, l);
        else ma = max(ma, l);
    }
    
    if(mi + ma > k) {
        if(len == -1 || ma + len > k) {
            type[c] = true;
            ans.push_back(c);
            return len;
        }
        type[c] = false;
        return len + ma;
    }
    if(mi+len > k) {
        type[c] = false;
        return 0;
    }
    type[c] = true;
    return len + mi;
}

void Solve() 
{
    cin>>n>>k;
    for (int i=1; i<n; i++){
        int a, b, c;
        cin>>a>>b>>c;
        
        adj[a-1].push_back({b-1, c});
        adj[b-1].push_back({a-1, c});
    }
    
    dfs(0, -1, -1);
    cout<<ans.size()<<"\n";
    for (auto x: ans)cout<<x +1 <<" ";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 35060 KB Output is correct
2 Correct 266 ms 34996 KB Output is correct
3 Correct 108 ms 17448 KB Output is correct
4 Correct 263 ms 34188 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7304 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 5 ms 7380 KB Output is correct
13 Correct 4 ms 7376 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7376 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7376 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 5 ms 7380 KB Output is correct
15 Correct 5 ms 7380 KB Output is correct
16 Correct 5 ms 7380 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 5 ms 7380 KB Output is correct
20 Correct 4 ms 7380 KB Output is correct
21 Correct 4 ms 7380 KB Output is correct
22 Correct 4 ms 7380 KB Output is correct
23 Correct 4 ms 7376 KB Output is correct
24 Correct 4 ms 7376 KB Output is correct
25 Correct 4 ms 7380 KB Output is correct
26 Correct 4 ms 7376 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 34928 KB Output is correct
2 Correct 112 ms 20424 KB Output is correct
3 Correct 118 ms 20760 KB Output is correct
4 Correct 97 ms 19008 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 196 ms 31260 KB Output is correct
8 Correct 196 ms 31200 KB Output is correct
9 Correct 193 ms 31248 KB Output is correct
10 Correct 193 ms 31280 KB Output is correct
11 Correct 266 ms 34912 KB Output is correct
12 Correct 149 ms 23768 KB Output is correct
13 Correct 93 ms 17596 KB Output is correct
14 Correct 140 ms 22716 KB Output is correct
15 Correct 195 ms 25912 KB Output is correct
16 Correct 215 ms 27204 KB Output is correct
17 Correct 166 ms 23976 KB Output is correct
18 Correct 161 ms 23612 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7508 KB Output is correct
2 Correct 6 ms 7580 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 7 ms 7648 KB Output is correct
6 Correct 5 ms 7644 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 5 ms 7676 KB Output is correct
9 Correct 5 ms 7588 KB Output is correct
10 Correct 5 ms 7636 KB Output is correct
11 Correct 5 ms 7636 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 5 ms 7636 KB Output is correct
14 Correct 5 ms 7636 KB Output is correct
15 Correct 5 ms 7508 KB Output is correct
16 Correct 4 ms 7392 KB Output is correct
17 Correct 5 ms 7392 KB Output is correct
18 Correct 6 ms 7508 KB Output is correct
19 Correct 5 ms 7508 KB Output is correct
20 Correct 4 ms 7388 KB Output is correct
21 Correct 7 ms 7508 KB Output is correct

Subtask #6
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 29788 KB Output is correct
2 Correct 234 ms 28712 KB Output is correct
3 Correct 251 ms 30224 KB Output is correct
4 Correct 89 ms 17868 KB Output is correct
5 Correct 251 ms 42284 KB Output is correct
6 Correct 268 ms 40708 KB Output is correct
7 Correct 262 ms 45076 KB Output is correct
8 Correct 255 ms 44000 KB Output is correct
9 Correct 243 ms 38340 KB Output is correct
10 Correct 300 ms 37392 KB Output is correct
11 Correct 292 ms 47456 KB Output is correct
12 Correct 180 ms 22800 KB Output is correct
13 Correct 298 ms 40148 KB Output is correct
14 Correct 290 ms 36560 KB Output is correct
15 Correct 257 ms 30476 KB Output is correct
16 Correct 239 ms 29064 KB Output is correct
17 Correct 226 ms 28864 KB Output is correct
18 Correct 266 ms 30424 KB Output is correct
19 Correct 166 ms 23356 KB Output is correct
20 Correct 86 ms 16416 KB Output is correct
21 Correct 275 ms 30400 KB Output is correct