oj.uz

Submission #899306

# Submission time Handle Problem Language Result Execution time Memory
899306 2024-01-05T17:23:21 Z LucaIlie Worst Reporter 4 (JOI21_worst_reporter4) C++17
14 / 100
 202 ms 196948 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5000;
const long long INF = 1e15;
int n;
int parent[MAX_N + 1], height[MAX_N + 1], cost[MAX_N + 1];
long long dp[MAX_N + 1][MAX_N + 1];
vector<int> children[MAX_N + 1];
map<int, int> mp;

void dfs( int u ) {
    for ( int v: children[u] )
        dfs( v );

    dp[u][n] = INF;
    for ( int x = n - 1; x >= 0; x-- ) {
        for ( int v: children[u] )
            dp[u][x] += dp[v][x];
        //dp[u][x] = min( dp[u][x], dp[u][x + 1] );
    }
    long long c = dp[u][height[u]];
    for ( int x = n - 1; x >= 0; x-- )
        dp[u][x] += cost[u];
    for ( int x = height[u]; x >= 0; x-- )
        dp[u][x] = min( dp[u][x], c );
}

int main() {
    cin >> n;
    for ( int v = 1; v <= n; v++ )
        cin >> parent[v] >> height[v] >> cost[v];

    for ( int v = 2; v <= n; v++ )
        children[parent[v]].push_back( v );

    for ( int v = 1; v <= n; v++ )
        mp[height[v]] = 1;
    int val = 0;
    for ( auto p: mp )
        mp[p.first] = val++;
    for ( int v = 1; v <= n; v++ )
        height[v] = mp[height[v]];

    dfs( 1 );

    cout << dp[1][0] << "\n";

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 118 ms 196436 KB Output is correct
6 Correct 73 ms 196180 KB Output is correct
7 Correct 73 ms 196240 KB Output is correct
8 Correct 93 ms 196468 KB Output is correct
9 Correct 73 ms 196176 KB Output is correct
10 Correct 73 ms 196180 KB Output is correct
11 Correct 71 ms 196368 KB Output is correct
12 Correct 126 ms 196784 KB Output is correct
13 Correct 115 ms 196948 KB Output is correct
14 Correct 123 ms 196828 KB Output is correct
15 Correct 115 ms 196436 KB Output is correct
16 Correct 83 ms 196532 KB Output is correct
17 Correct 75 ms 196640 KB Output is correct
18 Correct 70 ms 196176 KB Output is correct
19 Correct 144 ms 196700 KB Output is correct
20 Correct 123 ms 196364 KB Output is correct
21 Correct 128 ms 196396 KB Output is correct
22 Correct 202 ms 196432 KB Output is correct
23 Correct 194 ms 196180 KB Output is correct
24 Correct 160 ms 196596 KB Output is correct
25 Correct 153 ms 196496 KB Output is correct
26 Correct 125 ms 196780 KB Output is correct
27 Correct 104 ms 196644 KB Output is correct
28 Correct 121 ms 196688 KB Output is correct
29 Correct 128 ms 196688 KB Output is correct
30 Correct 125 ms 196688 KB Output is correct
31 Correct 135 ms 196688 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 118 ms 196436 KB Output is correct
6 Correct 73 ms 196180 KB Output is correct
7 Correct 73 ms 196240 KB Output is correct
8 Correct 93 ms 196468 KB Output is correct
9 Correct 73 ms 196176 KB Output is correct
10 Correct 73 ms 196180 KB Output is correct
11 Correct 71 ms 196368 KB Output is correct
12 Correct 126 ms 196784 KB Output is correct
13 Correct 115 ms 196948 KB Output is correct
14 Correct 123 ms 196828 KB Output is correct
15 Correct 115 ms 196436 KB Output is correct
16 Correct 83 ms 196532 KB Output is correct
17 Correct 75 ms 196640 KB Output is correct
18 Correct 70 ms 196176 KB Output is correct
19 Correct 144 ms 196700 KB Output is correct
20 Correct 123 ms 196364 KB Output is correct
21 Correct 128 ms 196396 KB Output is correct
22 Correct 202 ms 196432 KB Output is correct
23 Correct 194 ms 196180 KB Output is correct
24 Correct 160 ms 196596 KB Output is correct
25 Correct 153 ms 196496 KB Output is correct
26 Correct 125 ms 196780 KB Output is correct
27 Correct 104 ms 196644 KB Output is correct
28 Correct 121 ms 196688 KB Output is correct
29 Correct 128 ms 196688 KB Output is correct
30 Correct 125 ms 196688 KB Output is correct
31 Correct 135 ms 196688 KB Output is correct
32 Incorrect 40 ms 123216 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 118 ms 196436 KB Output is correct
6 Correct 73 ms 196180 KB Output is correct
7 Correct 73 ms 196240 KB Output is correct
8 Correct 93 ms 196468 KB Output is correct
9 Correct 73 ms 196176 KB Output is correct
10 Correct 73 ms 196180 KB Output is correct
11 Correct 71 ms 196368 KB Output is correct
12 Correct 126 ms 196784 KB Output is correct
13 Correct 115 ms 196948 KB Output is correct
14 Correct 123 ms 196828 KB Output is correct
15 Correct 115 ms 196436 KB Output is correct
16 Correct 83 ms 196532 KB Output is correct
17 Correct 75 ms 196640 KB Output is correct
18 Correct 70 ms 196176 KB Output is correct
19 Correct 144 ms 196700 KB Output is correct
20 Correct 123 ms 196364 KB Output is correct
21 Correct 128 ms 196396 KB Output is correct
22 Correct 202 ms 196432 KB Output is correct
23 Correct 194 ms 196180 KB Output is correct
24 Correct 160 ms 196596 KB Output is correct
25 Correct 153 ms 196496 KB Output is correct
26 Correct 125 ms 196780 KB Output is correct
27 Correct 104 ms 196644 KB Output is correct
28 Correct 121 ms 196688 KB Output is correct
29 Correct 128 ms 196688 KB Output is correct
30 Correct 125 ms 196688 KB Output is correct
31 Correct 135 ms 196688 KB Output is correct
32 Incorrect 40 ms 123216 KB Output isn't correct
33 Halted 0 ms 0 KB -