oj.uz

Submission #582647

# Submission time Handle Problem Language Result Execution time Memory
582647 2022-06-24T08:03:36 Z 박상훈(#8369) Magic Tree (CEOI19_magictree) C++17
34 / 100
 1467 ms 30768 KB 
#include <bits/stdc++.h>
#define int long long

typedef long long ll;
using namespace std;

vector<int> G[100100];
int par[100100], D[100100], W[100100];
int dp[100100][21];

void dfs(int s){
    for (auto &v:G[s]){
        dfs(v);
        vector<int> nxt(21);
        int curs = 0, curv = 0;
        for (int i=0;i<=20;i++){
            curs = max(curs, dp[s][i]);
            curv = max(curv, dp[v][i]);
            nxt[i] = max(nxt[i], curs + dp[v][i]);
            nxt[i] = max(nxt[i], curv + dp[s][i]);
        }
        for (int i=0;i<=20;i++) dp[s][i] = nxt[i];
    }

    if (D[s]){
        int mx = 0;
        for (int i=0;i<=D[s];i++) mx = max(mx, dp[s][i]);
        dp[s][D[s]] = max(dp[s][D[s]], mx + W[s]);
    }

    /*printf("%lld: ", s);
    for (int i=0;i<=9;i++) printf("%lld ", dp[s][i]);
    printf("\n");*/
}


signed main(){
    int n, m, k;
    scanf("%lld %lld %lld", &n, &m, &k);
    par[1] = -1;

    for (int i=2;i<=n;i++){
        scanf("%lld", par+i);
        G[par[i]].push_back(i);
    }

    for (int i=1;i<=m;i++){
        int v, d, w;
        scanf("%lld %lld %lld", &v, &d, &w);
        D[v] = d, W[v] = w;
    }

    dfs(1);
    printf("%lld\n", *max_element(dp[1], dp[1]+21));

    return 0;
}


/*tree.init();

    for (int i=n;i>=2;i--) if (D[i]){
        ll prv = tree.query(0, D[i]);
        tree.update(D[i], W[i] + prv);
    }

    printf("%lld\n", tree.tree[1]);*/

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%lld %lld %lld", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%lld", par+i);
      |         ~~~~~^~~~~~~~~~~~~~~
magictree.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%lld %lld %lld", &v, &d, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1467 ms 23268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2900 KB Output is correct
2 Incorrect 2 ms 2900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 23244 KB Output is correct
2 Correct 84 ms 23284 KB Output is correct
3 Correct 91 ms 26488 KB Output is correct
4 Correct 57 ms 22304 KB Output is correct
5 Correct 66 ms 30768 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 94 ms 23292 KB Output is correct
11 Correct 97 ms 23244 KB Output is correct
12 Correct 74 ms 26444 KB Output is correct
13 Correct 52 ms 22320 KB Output is correct
14 Correct 60 ms 30692 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 6896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2900 KB Output is correct
11 Incorrect 2 ms 2900 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Incorrect 1467 ms 23268 KB Output isn't correct
11 Halted 0 ms 0 KB -