oj.uz

Submission #1118336

# Submission time Handle Problem Language Result Execution time Memory
1118336 2024-11-25T10:21:21 Z alexdd Magic Tree (CEOI19_magictree) C++17
34 / 100
 1045 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k;
vector<int> con[100005];
int parent[100005];
int d[100005],w[100005];
vector<int> dp[100005];
void dfs(int nod)
{
    dp[nod].resize(k+2,0);
    for(int adj:con[nod])
    {
        dfs(adj);
        for(int i=1;i<=k;i++)
            dp[nod][i] += dp[adj][i];
    }
    //for(int i=d[nod];i<=k;i++)
      //  dp[nod][i] += w[nod];
    dp[nod][d[nod]] += w[nod];
    for(int i=1;i<=k;i++)
        dp[nod][i] = max(dp[nod][i], dp[nod][i-1]);
    //for(int i=1;i<=k;i++) cout<<nod<<" "<<i<<"  "<<dp[nod][i]<<" dp\n";
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>k;
    for(int i=2;i<=n;i++)
    {
        cin>>parent[i];
        con[parent[i]].push_back(i);
    }
    for(int i=1;i<=m;i++)
    {
        int x;
        cin>>x;
        cin>>d[x]>>w[x];
    }
    dfs(1);
    cout<<dp[1][k];
    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 955 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 16 ms 13408 KB Output is correct
2 Correct 20 ms 13408 KB Output is correct
3 Correct 16 ms 13408 KB Output is correct
4 Runtime error 731 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 66 ms 16156 KB Output is correct
2 Correct 62 ms 14588 KB Output is correct
3 Correct 50 ms 20016 KB Output is correct
4 Correct 32 ms 14556 KB Output is correct
5 Correct 55 ms 25164 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5468 KB Output is correct
2 Correct 3 ms 5468 KB Output is correct
3 Correct 3 ms 5468 KB Output is correct
4 Correct 3 ms 5468 KB Output is correct
5 Correct 4 ms 5468 KB Output is correct
6 Correct 3 ms 5468 KB Output is correct
7 Correct 5 ms 5480 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 4 ms 5468 KB Output is correct
10 Correct 82 ms 29536 KB Output is correct
11 Correct 61 ms 21532 KB Output is correct
12 Correct 60 ms 33368 KB Output is correct
13 Correct 41 ms 28116 KB Output is correct
14 Correct 51 ms 38568 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1045 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 3 ms 5468 KB Output is correct
2 Correct 3 ms 5468 KB Output is correct
3 Correct 3 ms 5468 KB Output is correct
4 Correct 3 ms 5468 KB Output is correct
5 Correct 4 ms 5468 KB Output is correct
6 Correct 3 ms 5468 KB Output is correct
7 Correct 5 ms 5480 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 4 ms 5468 KB Output is correct
10 Correct 16 ms 13408 KB Output is correct
11 Correct 20 ms 13408 KB Output is correct
12 Correct 16 ms 13408 KB Output is correct
13 Runtime error 731 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 3 ms 5468 KB Output is correct
2 Correct 3 ms 5468 KB Output is correct
3 Correct 3 ms 5468 KB Output is correct
4 Correct 3 ms 5468 KB Output is correct
5 Correct 4 ms 5468 KB Output is correct
6 Correct 3 ms 5468 KB Output is correct
7 Correct 5 ms 5480 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 4 ms 5468 KB Output is correct
10 Runtime error 955 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -