oj.uz

답안 #945785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
945785 2024-03-14T07:45:28 Z vjudge1 Magic Tree (CEOI19_magictree) C++17
34 / 100
 487 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 487 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8284 KB Output is correct
2 Correct 6 ms 8464 KB Output is correct
3 Correct 6 ms 8284 KB Output is correct
4 Runtime error 382 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 11604 KB Output is correct
2 Correct 39 ms 11604 KB Output is correct
3 Correct 49 ms 14932 KB Output is correct
4 Correct 27 ms 10700 KB Output is correct
5 Correct 37 ms 19536 KB Output is correct

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 75 ms 25804 KB Output is correct
11 Correct 61 ms 17756 KB Output is correct
12 Correct 82 ms 29008 KB Output is correct
13 Correct 51 ms 24532 KB Output is correct
14 Correct 49 ms 33628 KB Output is correct

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 355 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 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 8284 KB Output is correct
11 Correct 6 ms 8464 KB Output is correct
12 Correct 6 ms 8284 KB Output is correct
13 Runtime error 382 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 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 487 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -