oj.uz

Submission #582546

# Submission time Handle Problem Language Result Execution time Memory
582546 2022-06-24T05:07:52 Z 조영욱(#8372) Magic Tree (CEOI19_magictree) C++17
34 / 100
 99 ms 42904 KB 
#include <bits/stdc++.h>
using namespace std;

int n,m,k;
long long dp[100001][21];
vector<int> son[100001];
int t[100001];
int val[100001];

long long ans(int v,int d){
    if (dp[v][d]!=-1) {
        return dp[v][d];
    }
    long long ret=0;
    if (t[v]==d) {
        ret+=val[v];
    }
    for(int i=0;i<son[v].size();i++){
        long long temp=ans(son[v][i],d);
        if (t[son[v][i]]!=0&&t[son[v][i]]<=d) {
            temp=max(temp,ans(son[v][i],t[son[v][i]]));
        }
    ret+=temp;
    }
    return dp[v][d]=ret;
}

int main() {
    scanf("%d %d %d",&n,&m,&k);
    for(int i=2;i<=n;i++) {
        int p;
        scanf("%d",&p);
        son[p].push_back(i);
    }
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<m;i++) {
        int v,d,w;
        scanf("%d %d %d",&v,&d,&w);
        t[v]=d;
        val[v]=w;
    }
    printf("%lld",ans(1,k));
    return 0;
}

Compilation message

magictree.cpp: In function 'long long int ans(int, int)':
magictree.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i=0;i<son[v].size();i++){
      |                 ~^~~~~~~~~~~~~~
magictree.cpp: In function 'int main()':
magictree.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d %d %d",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
magictree.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d",&p);
      |         ~~~~~^~~~~~~~~
magictree.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%d %d %d",&v,&d,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 9 ms 18976 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 10 ms 19044 KB Output is correct
5 Correct 9 ms 19100 KB Output is correct
6 Correct 12 ms 19008 KB Output is correct
7 Correct 9 ms 19028 KB Output is correct
8 Correct 8 ms 19028 KB Output is correct
9 Correct 9 ms 19028 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 42904 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 21468 KB Output is correct
2 Correct 62 ms 21476 KB Output is correct
3 Correct 75 ms 26060 KB Output is correct
4 Correct 50 ms 20280 KB Output is correct
5 Correct 60 ms 32368 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 9 ms 18976 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 10 ms 19044 KB Output is correct
5 Correct 9 ms 19100 KB Output is correct
6 Correct 12 ms 19008 KB Output is correct
7 Correct 9 ms 19028 KB Output is correct
8 Correct 8 ms 19028 KB Output is correct
9 Correct 9 ms 19028 KB Output is correct
10 Correct 99 ms 21460 KB Output is correct
11 Correct 89 ms 21408 KB Output is correct
12 Correct 92 ms 26108 KB Output is correct
13 Correct 39 ms 20292 KB Output is correct
14 Correct 91 ms 32292 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

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

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 9 ms 18976 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 10 ms 19044 KB Output is correct
5 Correct 9 ms 19100 KB Output is correct
6 Correct 12 ms 19008 KB Output is correct
7 Correct 9 ms 19028 KB Output is correct
8 Correct 8 ms 19028 KB Output is correct
9 Correct 9 ms 19028 KB Output is correct
10 Runtime error 48 ms 42904 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -