oj.uz

Submission #589684

# Submission time Handle Problem Language Result Execution time Memory
589684 2022-07-05T06:24:31 Z Peti Worst Reporter 4 (JOI21_worst_reporter4) C++14
79 / 100
 446 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g;
vector<int> h, ert;
vector<map<int, long long>> mps;

void bejar(int akt){
    for(int x : g[akt]){
        bejar(x);
        if(mps[x].size() > mps[akt].size()) swap(mps[akt], mps[x]);
        for(auto p : mps[x]) mps[akt][p.first] += p.second;
    }
    auto it = mps[akt].find(h[akt]);
    if(it == mps[akt].end()){
        mps[akt][h[akt]] = ert[akt];
        it = mps[akt].find(h[akt]);
    } else{
        mps[akt][h[akt]] += ert[akt];
    }
    long long tmp = ert[akt];
    while(it != mps[akt].begin() && prev(it)->second < tmp){
        tmp -= prev(it)->second;
        mps[akt].erase(prev(it));
    }
    if(it != mps[akt].begin()) prev(it)->second -= tmp;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin>>n;

    g.resize(n);
    h.resize(n);
    ert.resize(n);
    mps.resize(n);
    for(int i = 0; i < n; i++){
        int a;
        cin>>a>>h[i]>>ert[i];
        --a;
        if(a != i) g[a].push_back(i);
    }

    bejar(0);
    long long meg = accumulate(ert.begin(), ert.end(), 0ll);
    for(auto p : mps[0]) meg -= p.second;
    cout<<meg<<'\n';

    return 0;
}

/*
6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6


20
15 62 418848971
13 5 277275513
14 60 80376452
12 14 256845164
12 42 481331310
6 86 290168639
3 98 947342135
3 19 896070909
16 39 48034188
8 29 925729089
18 97 420006994
13 51 454182928
19 61 822405612
13 37 148425187
15 77 474094143
14 27 272926693
18 43 566552069
9 93 790433300
10 73 61654171
14 28 334498030
*/

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1848 KB Output is correct
6 Correct 5 ms 1372 KB Output is correct
7 Correct 6 ms 1236 KB Output is correct
8 Correct 5 ms 1876 KB Output is correct
9 Correct 5 ms 1356 KB Output is correct
10 Correct 5 ms 1232 KB Output is correct
11 Correct 3 ms 972 KB Output is correct
12 Correct 4 ms 1608 KB Output is correct
13 Correct 3 ms 1492 KB Output is correct
14 Correct 4 ms 1236 KB Output is correct
15 Correct 6 ms 1236 KB Output is correct
16 Correct 7 ms 2248 KB Output is correct
17 Correct 6 ms 1612 KB Output is correct
18 Correct 3 ms 976 KB Output is correct
19 Correct 7 ms 1492 KB Output is correct
20 Correct 3 ms 1364 KB Output is correct
21 Correct 3 ms 1364 KB Output is correct
22 Correct 4 ms 1364 KB Output is correct
23 Correct 2 ms 1108 KB Output is correct
24 Correct 5 ms 1452 KB Output is correct
25 Correct 4 ms 1360 KB Output is correct
26 Correct 5 ms 1884 KB Output is correct
27 Correct 6 ms 1492 KB Output is correct
28 Correct 6 ms 1620 KB Output is correct
29 Correct 6 ms 1736 KB Output is correct
30 Correct 6 ms 1740 KB Output is correct
31 Correct 6 ms 1748 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1848 KB Output is correct
6 Correct 5 ms 1372 KB Output is correct
7 Correct 6 ms 1236 KB Output is correct
8 Correct 5 ms 1876 KB Output is correct
9 Correct 5 ms 1356 KB Output is correct
10 Correct 5 ms 1232 KB Output is correct
11 Correct 3 ms 972 KB Output is correct
12 Correct 4 ms 1608 KB Output is correct
13 Correct 3 ms 1492 KB Output is correct
14 Correct 4 ms 1236 KB Output is correct
15 Correct 6 ms 1236 KB Output is correct
16 Correct 7 ms 2248 KB Output is correct
17 Correct 6 ms 1612 KB Output is correct
18 Correct 3 ms 976 KB Output is correct
19 Correct 7 ms 1492 KB Output is correct
20 Correct 3 ms 1364 KB Output is correct
21 Correct 3 ms 1364 KB Output is correct
22 Correct 4 ms 1364 KB Output is correct
23 Correct 2 ms 1108 KB Output is correct
24 Correct 5 ms 1452 KB Output is correct
25 Correct 4 ms 1360 KB Output is correct
26 Correct 5 ms 1884 KB Output is correct
27 Correct 6 ms 1492 KB Output is correct
28 Correct 6 ms 1620 KB Output is correct
29 Correct 6 ms 1736 KB Output is correct
30 Correct 6 ms 1740 KB Output is correct
31 Correct 6 ms 1748 KB Output is correct
32 Correct 9 ms 1844 KB Output is correct
33 Correct 446 ms 78624 KB Output is correct
34 Correct 331 ms 53744 KB Output is correct
35 Correct 432 ms 75660 KB Output is correct
36 Correct 318 ms 53708 KB Output is correct
37 Correct 192 ms 34792 KB Output is correct
38 Correct 182 ms 30024 KB Output is correct
39 Correct 201 ms 52388 KB Output is correct
40 Correct 157 ms 52444 KB Output is correct
41 Correct 106 ms 52448 KB Output is correct
42 Correct 167 ms 39992 KB Output is correct
43 Correct 145 ms 39832 KB Output is correct
44 Correct 330 ms 103456 KB Output is correct
45 Correct 226 ms 68016 KB Output is correct
46 Correct 110 ms 30408 KB Output is correct
47 Correct 223 ms 49896 KB Output is correct
48 Correct 115 ms 42912 KB Output is correct
49 Correct 105 ms 42876 KB Output is correct
50 Correct 228 ms 46088 KB Output is correct
51 Correct 87 ms 33576 KB Output is correct
52 Correct 259 ms 50592 KB Output is correct
53 Correct 101 ms 43360 KB Output is correct
54 Correct 198 ms 65080 KB Output is correct
55 Correct 227 ms 51436 KB Output is correct
56 Correct 155 ms 56524 KB Output is correct
57 Correct 192 ms 59164 KB Output is correct
58 Correct 177 ms 57964 KB Output is correct
59 Correct 176 ms 58056 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1848 KB Output is correct
6 Correct 5 ms 1372 KB Output is correct
7 Correct 6 ms 1236 KB Output is correct
8 Correct 5 ms 1876 KB Output is correct
9 Correct 5 ms 1356 KB Output is correct
10 Correct 5 ms 1232 KB Output is correct
11 Correct 3 ms 972 KB Output is correct
12 Correct 4 ms 1608 KB Output is correct
13 Correct 3 ms 1492 KB Output is correct
14 Correct 4 ms 1236 KB Output is correct
15 Correct 6 ms 1236 KB Output is correct
16 Correct 7 ms 2248 KB Output is correct
17 Correct 6 ms 1612 KB Output is correct
18 Correct 3 ms 976 KB Output is correct
19 Correct 7 ms 1492 KB Output is correct
20 Correct 3 ms 1364 KB Output is correct
21 Correct 3 ms 1364 KB Output is correct
22 Correct 4 ms 1364 KB Output is correct
23 Correct 2 ms 1108 KB Output is correct
24 Correct 5 ms 1452 KB Output is correct
25 Correct 4 ms 1360 KB Output is correct
26 Correct 5 ms 1884 KB Output is correct
27 Correct 6 ms 1492 KB Output is correct
28 Correct 6 ms 1620 KB Output is correct
29 Correct 6 ms 1736 KB Output is correct
30 Correct 6 ms 1740 KB Output is correct
31 Correct 6 ms 1748 KB Output is correct
32 Correct 9 ms 1844 KB Output is correct
33 Correct 446 ms 78624 KB Output is correct
34 Correct 331 ms 53744 KB Output is correct
35 Correct 432 ms 75660 KB Output is correct
36 Correct 318 ms 53708 KB Output is correct
37 Correct 192 ms 34792 KB Output is correct
38 Correct 182 ms 30024 KB Output is correct
39 Correct 201 ms 52388 KB Output is correct
40 Correct 157 ms 52444 KB Output is correct
41 Correct 106 ms 52448 KB Output is correct
42 Correct 167 ms 39992 KB Output is correct
43 Correct 145 ms 39832 KB Output is correct
44 Correct 330 ms 103456 KB Output is correct
45 Correct 226 ms 68016 KB Output is correct
46 Correct 110 ms 30408 KB Output is correct
47 Correct 223 ms 49896 KB Output is correct
48 Correct 115 ms 42912 KB Output is correct
49 Correct 105 ms 42876 KB Output is correct
50 Correct 228 ms 46088 KB Output is correct
51 Correct 87 ms 33576 KB Output is correct
52 Correct 259 ms 50592 KB Output is correct
53 Correct 101 ms 43360 KB Output is correct
54 Correct 198 ms 65080 KB Output is correct
55 Correct 227 ms 51436 KB Output is correct
56 Correct 155 ms 56524 KB Output is correct
57 Correct 192 ms 59164 KB Output is correct
58 Correct 177 ms 57964 KB Output is correct
59 Correct 176 ms 58056 KB Output is correct
60 Runtime error 326 ms 524288 KB Execution killed with signal 9
61 Halted 0 ms 0 KB -