oj.uz

Submission #518919

# Submission time Handle Problem Language Result Execution time Memory
518919 2022-01-25T07:23:37 Z ParsaAlizadeh Worst Reporter 4 (JOI21_worst_reporter4) C++17
14 / 100
 191 ms 118200 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define all(x) begin(x), end(x)
#define kill(x) return cout << x << '\n', 0
#define fst first
#define snd second

void assume(int expr) {
    if (!expr) __builtin_unreachable();
}

constexpr int N = 5e3 + 10;

int n;
ll H[N], C[N], dp[N][N];
vector<int> adj[N];

void dfs(int u) {
    static vector<int> st = {0};
    st.push_back(u);
    for (int v : adj[u])
        dfs(v);
    for (int j = 0; j+1 < st.size(); j++) {
        dp[u][j] = C[u];
        for (int v : adj[u])
            dp[u][j] += dp[v][j];
        if (H[u] >= H[st[j]]) {
            ll tmp = 0;
            for (int v : adj[u])
                tmp += dp[v][st.size()-1];
            dp[u][j] = min(dp[u][j], tmp);
        }
        // cout << u << ' ' << j << ' ' << st[j] << ' ' << dp[u][j] << endl;
    }
    st.pop_back();
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    assert(n < N);
    for (int i = 1; i <= n; i++) {
        int par;
        cin >> par >> H[i] >> C[i];
        if (i > 1)
            adj[par].push_back(i);
    }
    dfs(1);
    cout << dp[1][0] << '\n';
    return 0;
}

Compilation message

worst_reporter2.cpp: In function 'void dfs(int)':
worst_reporter2.cpp:27:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int j = 0; j+1 < st.size(); j++) {
      |                     ~~~~^~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 11 ms 21204 KB Output is correct
6 Correct 11 ms 21264 KB Output is correct
7 Correct 11 ms 21228 KB Output is correct
8 Correct 11 ms 21196 KB Output is correct
9 Correct 11 ms 21196 KB Output is correct
10 Correct 11 ms 21196 KB Output is correct
11 Correct 11 ms 21240 KB Output is correct
12 Correct 99 ms 118112 KB Output is correct
13 Correct 98 ms 118104 KB Output is correct
14 Correct 52 ms 70044 KB Output is correct
15 Correct 56 ms 70084 KB Output is correct
16 Correct 10 ms 21324 KB Output is correct
17 Correct 11 ms 21244 KB Output is correct
18 Correct 11 ms 21324 KB Output is correct
19 Correct 55 ms 69956 KB Output is correct
20 Correct 56 ms 69904 KB Output is correct
21 Correct 55 ms 69956 KB Output is correct
22 Correct 10 ms 20892 KB Output is correct
23 Correct 9 ms 20940 KB Output is correct
24 Correct 191 ms 94688 KB Output is correct
25 Correct 144 ms 94380 KB Output is correct
26 Correct 64 ms 118200 KB Output is correct
27 Correct 30 ms 48356 KB Output is correct
28 Correct 48 ms 74184 KB Output is correct
29 Correct 71 ms 99820 KB Output is correct
30 Correct 44 ms 69960 KB Output is correct
31 Correct 45 ms 69968 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 11 ms 21204 KB Output is correct
6 Correct 11 ms 21264 KB Output is correct
7 Correct 11 ms 21228 KB Output is correct
8 Correct 11 ms 21196 KB Output is correct
9 Correct 11 ms 21196 KB Output is correct
10 Correct 11 ms 21196 KB Output is correct
11 Correct 11 ms 21240 KB Output is correct
12 Correct 99 ms 118112 KB Output is correct
13 Correct 98 ms 118104 KB Output is correct
14 Correct 52 ms 70044 KB Output is correct
15 Correct 56 ms 70084 KB Output is correct
16 Correct 10 ms 21324 KB Output is correct
17 Correct 11 ms 21244 KB Output is correct
18 Correct 11 ms 21324 KB Output is correct
19 Correct 55 ms 69956 KB Output is correct
20 Correct 56 ms 69904 KB Output is correct
21 Correct 55 ms 69956 KB Output is correct
22 Correct 10 ms 20892 KB Output is correct
23 Correct 9 ms 20940 KB Output is correct
24 Correct 191 ms 94688 KB Output is correct
25 Correct 144 ms 94380 KB Output is correct
26 Correct 64 ms 118200 KB Output is correct
27 Correct 30 ms 48356 KB Output is correct
28 Correct 48 ms 74184 KB Output is correct
29 Correct 71 ms 99820 KB Output is correct
30 Correct 44 ms 69960 KB Output is correct
31 Correct 45 ms 69968 KB Output is correct
32 Correct 11 ms 21192 KB Output is correct
33 Runtime error 4 ms 716 KB Execution killed with signal 6
34 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 11 ms 21204 KB Output is correct
6 Correct 11 ms 21264 KB Output is correct
7 Correct 11 ms 21228 KB Output is correct
8 Correct 11 ms 21196 KB Output is correct
9 Correct 11 ms 21196 KB Output is correct
10 Correct 11 ms 21196 KB Output is correct
11 Correct 11 ms 21240 KB Output is correct
12 Correct 99 ms 118112 KB Output is correct
13 Correct 98 ms 118104 KB Output is correct
14 Correct 52 ms 70044 KB Output is correct
15 Correct 56 ms 70084 KB Output is correct
16 Correct 10 ms 21324 KB Output is correct
17 Correct 11 ms 21244 KB Output is correct
18 Correct 11 ms 21324 KB Output is correct
19 Correct 55 ms 69956 KB Output is correct
20 Correct 56 ms 69904 KB Output is correct
21 Correct 55 ms 69956 KB Output is correct
22 Correct 10 ms 20892 KB Output is correct
23 Correct 9 ms 20940 KB Output is correct
24 Correct 191 ms 94688 KB Output is correct
25 Correct 144 ms 94380 KB Output is correct
26 Correct 64 ms 118200 KB Output is correct
27 Correct 30 ms 48356 KB Output is correct
28 Correct 48 ms 74184 KB Output is correct
29 Correct 71 ms 99820 KB Output is correct
30 Correct 44 ms 69960 KB Output is correct
31 Correct 45 ms 69968 KB Output is correct
32 Correct 11 ms 21192 KB Output is correct
33 Runtime error 4 ms 716 KB Execution killed with signal 6
34 Halted 0 ms 0 KB -