oj.uz

Submission #255336

# Submission time Handle Problem Language Result Execution time Memory
255336 2020-07-31T17:39:42 Z model_code Firefighting (NOI20_firefighting) C++17
100 / 100
 439 ms 50024 KB 
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1'000'000;
vector<pair<int, int>> adjlist[MAXN];
long long k;
vector<int> ans;
pair<bool, long long> dfs(int index, int prev,long long dist) {
    long long max_overflow=numeric_limits<long long>::min();
    long long max_underflow=0;
    for(const pair<int,int>& pr : adjlist[index]) {
        if(pr.first!=prev){
            pair<bool, long long> res=dfs(pr.first,index,pr.second);
            if(res.first){
                max_overflow=max(max_overflow,res.second);
            }
            else {
                max_underflow=max(max_underflow,res.second);
            }
        }
    }
    pair<bool, long long> ret;
    if(max_overflow>=max_underflow){
        ret={true,max_overflow-dist};
    }
    else {
        ret={false,max_underflow+dist};
    }
    if(!ret.first&&ret.second>k){
        ans.push_back(index);
        ret={true,k-dist};
    }
    if(ret.first&&ret.second<0){
        ret={false,0};
    }
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n>>k;
    for(int i=1;i<n;++i){
        int a,b,w;
        cin>>a>>b>>w;
        --a;--b;
        adjlist[a].emplace_back(b,w);
        adjlist[b].emplace_back(a,w);
    }
    dfs(0,-1,numeric_limits<long long>::max()>>2);
    cout<<ans.size()<<'\n';
    auto it=ans.begin();
    cout<<(*it+1);
    for(++it;it!=ans.end();++it){
        cout<<' '<<(*it+1);
    }
    cout<<'\n';
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 38116 KB Output is correct
2 Correct 337 ms 38376 KB Output is correct
3 Correct 103 ms 29168 KB Output is correct
4 Correct 340 ms 37860 KB Output is correct
5 Correct 16 ms 23808 KB Output is correct
6 Correct 15 ms 23808 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 38120 KB Output is correct
2 Correct 147 ms 30972 KB Output is correct
3 Correct 219 ms 31224 KB Output is correct
4 Correct 174 ms 30196 KB Output is correct
5 Correct 17 ms 23808 KB Output is correct
6 Correct 17 ms 23808 KB Output is correct
7 Correct 362 ms 36964 KB Output is correct
8 Correct 316 ms 37092 KB Output is correct
9 Correct 262 ms 36964 KB Output is correct
10 Correct 260 ms 36964 KB Output is correct
11 Correct 338 ms 38196 KB Output is correct
12 Correct 207 ms 32880 KB Output is correct
13 Correct 106 ms 29552 KB Output is correct
14 Correct 181 ms 32500 KB Output is correct
15 Correct 225 ms 34156 KB Output is correct
16 Correct 337 ms 34676 KB Output is correct
17 Correct 204 ms 32884 KB Output is correct
18 Correct 198 ms 32628 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23936 KB Output is correct
2 Correct 15 ms 23936 KB Output is correct
3 Correct 15 ms 23808 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 19 ms 24064 KB Output is correct
6 Correct 16 ms 24064 KB Output is correct
7 Correct 19 ms 24064 KB Output is correct
8 Correct 19 ms 24064 KB Output is correct
9 Correct 16 ms 24064 KB Output is correct
10 Correct 26 ms 24064 KB Output is correct
11 Correct 16 ms 24064 KB Output is correct
12 Correct 15 ms 23936 KB Output is correct
13 Correct 16 ms 24064 KB Output is correct
14 Correct 15 ms 23936 KB Output is correct
15 Correct 16 ms 23936 KB Output is correct
16 Correct 16 ms 23936 KB Output is correct
17 Correct 15 ms 23936 KB Output is correct
18 Correct 20 ms 23936 KB Output is correct
19 Correct 16 ms 23936 KB Output is correct
20 Correct 16 ms 23936 KB Output is correct
21 Correct 19 ms 23936 KB Output is correct

Subtask #6
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 34560 KB Output is correct
2 Correct 309 ms 34040 KB Output is correct
3 Correct 300 ms 34808 KB Output is correct
4 Correct 129 ms 28924 KB Output is correct
5 Correct 314 ms 46444 KB Output is correct
6 Correct 377 ms 45032 KB Output is correct
7 Correct 310 ms 48880 KB Output is correct
8 Correct 361 ms 48092 KB Output is correct
9 Correct 304 ms 42748 KB Output is correct
10 Correct 310 ms 41976 KB Output is correct
11 Correct 320 ms 50024 KB Output is correct
12 Correct 186 ms 31224 KB Output is correct
13 Correct 352 ms 44360 KB Output is correct
14 Correct 316 ms 40444 KB Output is correct
15 Correct 302 ms 34936 KB Output is correct
16 Correct 295 ms 34168 KB Output is correct
17 Correct 278 ms 34168 KB Output is correct
18 Correct 306 ms 35064 KB Output is correct
19 Correct 253 ms 31480 KB Output is correct
20 Correct 131 ms 28280 KB Output is correct
21 Correct 388 ms 34808 KB Output is correct