oj.uz

Submission #418192

# Submission time Handle Problem Language Result Execution time Memory
418192 2021-06-05T08:04:26 Z lyc Worst Reporter 4 (JOI21_worst_reporter4) C++14
79 / 100
 478 ms 117704 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;

const int mxN = 2e5+5;

int N, A[mxN], H[mxN], C[mxN], V;
vector<int> al[mxN], vals;

map<int,ll> dp[mxN];

void dfs(int u) {
    //FOR(x,0,V-1) dp[u][x] = 0;

    dp[u].insert(make_pair(0,0));
    for (int v : al[u]) {
        dfs(v);

        //FOR(x,0,V-1){
        //    ll cur = dp[v][x] + C[v];
        //    if (x <= H[v]) cur = min(cur, dp[v][H[v]]);
        //    dp[u][x] += cur;
        //}

        if (dp[v].count(H[v]+1)) dp[v][H[v]+1] += C[v];
        else dp[v].insert(make_pair(H[v]+1, C[v]));
        
        if (0 < H[v]) {
            if (dp[v].count(0)) dp[v][0] += C[v];
            else dp[v].insert(make_pair(0,C[v]));

            auto it = --dp[v].lower_bound(H[v]+1);
            while (it != dp[v].begin() && it->second <= C[v]) {
                auto x = prev(it);
                x->second += it->second;
                dp[v].erase(it);
                it = x;
            }
            it->second -= C[v];
        }

    //cout << u << " to " << v << ": ";
    //for (auto& x : dp[v]) {
    //    cout << vals[x.first] << " " << x.second << ", ";
    //}
    //cout << endl;

        if (SZ(dp[v]) > SZ(dp[u])) swap(dp[v],dp[u]);
        for (auto& x : dp[v]) {
            if (dp[u].count(x.first)) dp[u][x.first] += x.second;
            else dp[u].insert(x);
        }
    }

    //cout << u << ": ";
    //for (auto& x : dp[u]) {
    //    cout << x.first << " " << x.second << ", ";
    //}
    //cout << endl;
}

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

    cin >> N;
    FOR(i,1,N){
        cin >> A[i] >> H[i] >> C[i];
        if (i != 1) al[A[i]].push_back(i);
        vals.push_back(H[i]);
    }

    vals.push_back(1);
    sort(ALL(vals));
    vals.resize(unique(ALL(vals))-vals.begin());
    FOR(i,1,N){
        H[i] = lower_bound(ALL(vals),H[i])-vals.begin();
    }
    V = SZ(vals);

    dfs(1);

    //cout << min(dp[1][0] + C[1], dp[1][H[1]]) << '\n';
    ll ans = 1e18, cur = 0;
    for (auto& x : dp[1]) {
        if (x.first > 0) ans = min(ans, cur + C[1]);
        if (x.first > H[1]) ans = min(ans, cur);
        cur += x.second;
    }
    ans = min(ans, cur + C[1]);
    if (dp[1].rbegin()->first >= H[1]) ans = min(ans, cur);

    cout << ans << '\n';
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14348 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14332 KB Output is correct
5 Correct 16 ms 15964 KB Output is correct
6 Correct 14 ms 15456 KB Output is correct
7 Correct 13 ms 15308 KB Output is correct
8 Correct 16 ms 15952 KB Output is correct
9 Correct 14 ms 15444 KB Output is correct
10 Correct 13 ms 15320 KB Output is correct
11 Correct 12 ms 15052 KB Output is correct
12 Correct 14 ms 15944 KB Output is correct
13 Correct 12 ms 15820 KB Output is correct
14 Correct 14 ms 15448 KB Output is correct
15 Correct 13 ms 15444 KB Output is correct
16 Correct 16 ms 16244 KB Output is correct
17 Correct 15 ms 15820 KB Output is correct
18 Correct 12 ms 15144 KB Output is correct
19 Correct 14 ms 15692 KB Output is correct
20 Correct 12 ms 15564 KB Output is correct
21 Correct 12 ms 15564 KB Output is correct
22 Correct 13 ms 15564 KB Output is correct
23 Correct 11 ms 15272 KB Output is correct
24 Correct 14 ms 15684 KB Output is correct
25 Correct 12 ms 15564 KB Output is correct
26 Correct 12 ms 15948 KB Output is correct
27 Correct 14 ms 15704 KB Output is correct
28 Correct 14 ms 15820 KB Output is correct
29 Correct 13 ms 15948 KB Output is correct
30 Correct 14 ms 15868 KB Output is correct
31 Correct 14 ms 15948 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14348 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14332 KB Output is correct
5 Correct 16 ms 15964 KB Output is correct
6 Correct 14 ms 15456 KB Output is correct
7 Correct 13 ms 15308 KB Output is correct
8 Correct 16 ms 15952 KB Output is correct
9 Correct 14 ms 15444 KB Output is correct
10 Correct 13 ms 15320 KB Output is correct
11 Correct 12 ms 15052 KB Output is correct
12 Correct 14 ms 15944 KB Output is correct
13 Correct 12 ms 15820 KB Output is correct
14 Correct 14 ms 15448 KB Output is correct
15 Correct 13 ms 15444 KB Output is correct
16 Correct 16 ms 16244 KB Output is correct
17 Correct 15 ms 15820 KB Output is correct
18 Correct 12 ms 15144 KB Output is correct
19 Correct 14 ms 15692 KB Output is correct
20 Correct 12 ms 15564 KB Output is correct
21 Correct 12 ms 15564 KB Output is correct
22 Correct 13 ms 15564 KB Output is correct
23 Correct 11 ms 15272 KB Output is correct
24 Correct 14 ms 15684 KB Output is correct
25 Correct 12 ms 15564 KB Output is correct
26 Correct 12 ms 15948 KB Output is correct
27 Correct 14 ms 15704 KB Output is correct
28 Correct 14 ms 15820 KB Output is correct
29 Correct 13 ms 15948 KB Output is correct
30 Correct 14 ms 15868 KB Output is correct
31 Correct 14 ms 15948 KB Output is correct
32 Correct 15 ms 15960 KB Output is correct
33 Correct 478 ms 92860 KB Output is correct
34 Correct 349 ms 67888 KB Output is correct
35 Correct 466 ms 89776 KB Output is correct
36 Correct 367 ms 67852 KB Output is correct
37 Correct 238 ms 48924 KB Output is correct
38 Correct 209 ms 44380 KB Output is correct
39 Correct 276 ms 75892 KB Output is correct
40 Correct 213 ms 75832 KB Output is correct
41 Correct 152 ms 75868 KB Output is correct
42 Correct 247 ms 58736 KB Output is correct
43 Correct 214 ms 58708 KB Output is correct
44 Correct 474 ms 117704 KB Output is correct
45 Correct 337 ms 82112 KB Output is correct
46 Correct 146 ms 44464 KB Output is correct
47 Correct 378 ms 68660 KB Output is correct
48 Correct 203 ms 61616 KB Output is correct
49 Correct 148 ms 61696 KB Output is correct
50 Correct 378 ms 60148 KB Output is correct
51 Correct 175 ms 47656 KB Output is correct
52 Correct 447 ms 69256 KB Output is correct
53 Correct 198 ms 62244 KB Output is correct
54 Correct 165 ms 76004 KB Output is correct
55 Correct 335 ms 70180 KB Output is correct
56 Correct 309 ms 77612 KB Output is correct
57 Correct 294 ms 81332 KB Output is correct
58 Correct 319 ms 76692 KB Output is correct
59 Correct 333 ms 76724 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14348 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14332 KB Output is correct
5 Correct 16 ms 15964 KB Output is correct
6 Correct 14 ms 15456 KB Output is correct
7 Correct 13 ms 15308 KB Output is correct
8 Correct 16 ms 15952 KB Output is correct
9 Correct 14 ms 15444 KB Output is correct
10 Correct 13 ms 15320 KB Output is correct
11 Correct 12 ms 15052 KB Output is correct
12 Correct 14 ms 15944 KB Output is correct
13 Correct 12 ms 15820 KB Output is correct
14 Correct 14 ms 15448 KB Output is correct
15 Correct 13 ms 15444 KB Output is correct
16 Correct 16 ms 16244 KB Output is correct
17 Correct 15 ms 15820 KB Output is correct
18 Correct 12 ms 15144 KB Output is correct
19 Correct 14 ms 15692 KB Output is correct
20 Correct 12 ms 15564 KB Output is correct
21 Correct 12 ms 15564 KB Output is correct
22 Correct 13 ms 15564 KB Output is correct
23 Correct 11 ms 15272 KB Output is correct
24 Correct 14 ms 15684 KB Output is correct
25 Correct 12 ms 15564 KB Output is correct
26 Correct 12 ms 15948 KB Output is correct
27 Correct 14 ms 15704 KB Output is correct
28 Correct 14 ms 15820 KB Output is correct
29 Correct 13 ms 15948 KB Output is correct
30 Correct 14 ms 15868 KB Output is correct
31 Correct 14 ms 15948 KB Output is correct
32 Correct 15 ms 15960 KB Output is correct
33 Correct 478 ms 92860 KB Output is correct
34 Correct 349 ms 67888 KB Output is correct
35 Correct 466 ms 89776 KB Output is correct
36 Correct 367 ms 67852 KB Output is correct
37 Correct 238 ms 48924 KB Output is correct
38 Correct 209 ms 44380 KB Output is correct
39 Correct 276 ms 75892 KB Output is correct
40 Correct 213 ms 75832 KB Output is correct
41 Correct 152 ms 75868 KB Output is correct
42 Correct 247 ms 58736 KB Output is correct
43 Correct 214 ms 58708 KB Output is correct
44 Correct 474 ms 117704 KB Output is correct
45 Correct 337 ms 82112 KB Output is correct
46 Correct 146 ms 44464 KB Output is correct
47 Correct 378 ms 68660 KB Output is correct
48 Correct 203 ms 61616 KB Output is correct
49 Correct 148 ms 61696 KB Output is correct
50 Correct 378 ms 60148 KB Output is correct
51 Correct 175 ms 47656 KB Output is correct
52 Correct 447 ms 69256 KB Output is correct
53 Correct 198 ms 62244 KB Output is correct
54 Correct 165 ms 76004 KB Output is correct
55 Correct 335 ms 70180 KB Output is correct
56 Correct 309 ms 77612 KB Output is correct
57 Correct 294 ms 81332 KB Output is correct
58 Correct 319 ms 76692 KB Output is correct
59 Correct 333 ms 76724 KB Output is correct
60 Correct 9 ms 14412 KB Output is correct
61 Incorrect 9 ms 14404 KB Output isn't correct
62 Halted 0 ms 0 KB -