oj.uz

Submission #582542

# Submission time Handle Problem Language Result Execution time Memory
582542 2022-06-24T04:52:27 Z 조영욱(#8372) Magic Tree (CEOI19_magictree) C++17
34 / 100
 1959 ms 44004 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=0;
        for(int j=1;j<=d;j++) {
            temp=max(temp,ans(son[v][i],j));
        }
    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 10 ms 19028 KB Output is correct
2 Correct 9 ms 18988 KB Output is correct
3 Correct 8 ms 19048 KB Output is correct
4 Correct 8 ms 19028 KB Output is correct
5 Correct 8 ms 19028 KB Output is correct
6 Correct 8 ms 19028 KB Output is correct
7 Correct 8 ms 19104 KB Output is correct
8 Correct 9 ms 19044 KB Output is correct
9 Correct 9 ms 18984 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19156 KB Output is correct
2 Incorrect 9 ms 19236 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 73 ms 23536 KB Output is correct
2 Correct 70 ms 23504 KB Output is correct
3 Correct 69 ms 28236 KB Output is correct
4 Correct 51 ms 22132 KB Output is correct
5 Correct 71 ms 34532 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 9 ms 18988 KB Output is correct
3 Correct 8 ms 19048 KB Output is correct
4 Correct 8 ms 19028 KB Output is correct
5 Correct 8 ms 19028 KB Output is correct
6 Correct 8 ms 19028 KB Output is correct
7 Correct 8 ms 19104 KB Output is correct
8 Correct 9 ms 19044 KB Output is correct
9 Correct 9 ms 18984 KB Output is correct
10 Correct 386 ms 22940 KB Output is correct
11 Correct 167 ms 22900 KB Output is correct
12 Correct 287 ms 27596 KB Output is correct
13 Correct 95 ms 21400 KB Output is correct
14 Correct 165 ms 33852 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

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

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 9 ms 18988 KB Output is correct
3 Correct 8 ms 19048 KB Output is correct
4 Correct 8 ms 19028 KB Output is correct
5 Correct 8 ms 19028 KB Output is correct
6 Correct 8 ms 19028 KB Output is correct
7 Correct 8 ms 19104 KB Output is correct
8 Correct 9 ms 19044 KB Output is correct
9 Correct 9 ms 18984 KB Output is correct
10 Runtime error 1083 ms 44004 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -