oj.uz

Submission #945577

# Submission time Handle Problem Language Result Execution time Memory
945577 2024-03-14T05:02:46 Z vjudge1 Magic Tree (CEOI19_magictree) C++17
34 / 100
 497 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k; cin >> n >> m >> k;
    vector <vector<int>> G(n);
    for ( int i = 1; i < n; i++ ){
        int p; cin >> p;
        --p;
        G[p].pb(i);
    }
    vector <int> w(n), d(n);
    for ( int i = 0; i < m; i++ ){
        int d_, v, w_; cin >> v >> d_ >> w_;
        --v;
        w[v] = w_;
        d[v] = d_;
    }
    vector <vector<int>> dp(n, vector <int> (k + 1));
    auto dfs = [&](auto dfs, int u) -> void{
        for ( auto &v: G[u] ){
            dfs(dfs, v);
        }
        for ( int j = 1; j <= k; j++ ){
            int opt = 0;
            for ( auto &v: G[u] ){
                opt += dp[v][j];
            }
            chmax(dp[u][j], dp[u][j - 1]);
            if ( j <= d[u] ){
                chmax(dp[u][d[u]], opt + w[u]);
            }
            chmax(dp[u][j], opt);
        }
    };
    dfs(dfs, 0);
    cout << dp[0][k];

    cout << '\n';
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 497 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8280 KB Output is correct
2 Correct 6 ms 8284 KB Output is correct
3 Correct 6 ms 8284 KB Output is correct
4 Runtime error 381 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 11604 KB Output is correct
2 Correct 40 ms 13580 KB Output is correct
3 Correct 50 ms 16976 KB Output is correct
4 Correct 29 ms 11988 KB Output is correct
5 Correct 41 ms 21828 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 74 ms 25700 KB Output is correct
11 Correct 60 ms 19284 KB Output is correct
12 Correct 61 ms 30808 KB Output is correct
13 Correct 45 ms 25840 KB Output is correct
14 Correct 47 ms 35156 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 361 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 6 ms 8280 KB Output is correct
11 Correct 6 ms 8284 KB Output is correct
12 Correct 6 ms 8284 KB Output is correct
13 Runtime error 381 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Runtime error 497 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -