oj.uz

Submission #899309

# Submission time Handle Problem Language Result Execution time Memory
899309 2024-01-05T18:02:11 Z LucaIlie Worst Reporter 4 (JOI21_worst_reporter4) C++17
14 / 100
 196 ms 196852 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 = height[u]; x >= 0; x-- )
        dp[u][x] = min( dp[u][x], c - cost[u] );
}

int main() {
    long long c = 0;

    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, c += cost[v];
    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 << c + 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 92 ms 196172 KB Output is correct
6 Correct 66 ms 195920 KB Output is correct
7 Correct 62 ms 194384 KB Output is correct
8 Correct 74 ms 195476 KB Output is correct
9 Correct 62 ms 195156 KB Output is correct
10 Correct 62 ms 193872 KB Output is correct
11 Correct 61 ms 195920 KB Output is correct
12 Correct 113 ms 196688 KB Output is correct
13 Correct 100 ms 196432 KB Output is correct
14 Correct 110 ms 196632 KB Output is correct
15 Correct 100 ms 196336 KB Output is correct
16 Correct 68 ms 196176 KB Output is correct
17 Correct 57 ms 195668 KB Output is correct
18 Correct 58 ms 195664 KB Output is correct
19 Correct 108 ms 158032 KB Output is correct
20 Correct 78 ms 110160 KB Output is correct
21 Correct 77 ms 109416 KB Output is correct
22 Correct 196 ms 196180 KB Output is correct
23 Correct 192 ms 195528 KB Output is correct
24 Correct 154 ms 196444 KB Output is correct
25 Correct 140 ms 195760 KB Output is correct
26 Correct 109 ms 196852 KB Output is correct
27 Correct 113 ms 195924 KB Output is correct
28 Correct 112 ms 195892 KB Output is correct
29 Correct 107 ms 194276 KB Output is correct
30 Correct 110 ms 196692 KB Output is correct
31 Correct 108 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 92 ms 196172 KB Output is correct
6 Correct 66 ms 195920 KB Output is correct
7 Correct 62 ms 194384 KB Output is correct
8 Correct 74 ms 195476 KB Output is correct
9 Correct 62 ms 195156 KB Output is correct
10 Correct 62 ms 193872 KB Output is correct
11 Correct 61 ms 195920 KB Output is correct
12 Correct 113 ms 196688 KB Output is correct
13 Correct 100 ms 196432 KB Output is correct
14 Correct 110 ms 196632 KB Output is correct
15 Correct 100 ms 196336 KB Output is correct
16 Correct 68 ms 196176 KB Output is correct
17 Correct 57 ms 195668 KB Output is correct
18 Correct 58 ms 195664 KB Output is correct
19 Correct 108 ms 158032 KB Output is correct
20 Correct 78 ms 110160 KB Output is correct
21 Correct 77 ms 109416 KB Output is correct
22 Correct 196 ms 196180 KB Output is correct
23 Correct 192 ms 195528 KB Output is correct
24 Correct 154 ms 196444 KB Output is correct
25 Correct 140 ms 195760 KB Output is correct
26 Correct 109 ms 196852 KB Output is correct
27 Correct 113 ms 195924 KB Output is correct
28 Correct 112 ms 195892 KB Output is correct
29 Correct 107 ms 194276 KB Output is correct
30 Correct 110 ms 196692 KB Output is correct
31 Correct 108 ms 196688 KB Output is correct
32 Incorrect 39 ms 122196 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 92 ms 196172 KB Output is correct
6 Correct 66 ms 195920 KB Output is correct
7 Correct 62 ms 194384 KB Output is correct
8 Correct 74 ms 195476 KB Output is correct
9 Correct 62 ms 195156 KB Output is correct
10 Correct 62 ms 193872 KB Output is correct
11 Correct 61 ms 195920 KB Output is correct
12 Correct 113 ms 196688 KB Output is correct
13 Correct 100 ms 196432 KB Output is correct
14 Correct 110 ms 196632 KB Output is correct
15 Correct 100 ms 196336 KB Output is correct
16 Correct 68 ms 196176 KB Output is correct
17 Correct 57 ms 195668 KB Output is correct
18 Correct 58 ms 195664 KB Output is correct
19 Correct 108 ms 158032 KB Output is correct
20 Correct 78 ms 110160 KB Output is correct
21 Correct 77 ms 109416 KB Output is correct
22 Correct 196 ms 196180 KB Output is correct
23 Correct 192 ms 195528 KB Output is correct
24 Correct 154 ms 196444 KB Output is correct
25 Correct 140 ms 195760 KB Output is correct
26 Correct 109 ms 196852 KB Output is correct
27 Correct 113 ms 195924 KB Output is correct
28 Correct 112 ms 195892 KB Output is correct
29 Correct 107 ms 194276 KB Output is correct
30 Correct 110 ms 196692 KB Output is correct
31 Correct 108 ms 196688 KB Output is correct
32 Incorrect 39 ms 122196 KB Output isn't correct
33 Halted 0 ms 0 KB -