oj.uz

Submission #775727

# Submission time Handle Problem Language Result Execution time Memory
775727 2023-07-06T20:25:48 Z danikoynov Magic Tree (CEOI19_magictree) C++14
34 / 100
 1903 ms 44788 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10, maxk = 21;
int n, m, k, p[maxn], w[maxn], d[maxn];
ll dp[maxn][maxk];
vector < int > adj[maxn];

void dfs(int v)
{
    for (int u : adj[v])
    {
        dfs(u);
        for (int j = 1; j <= k; j ++)
        {
            dp[v][j] += dp[u][j];
        }
    }

    if (d[v] != 0)
        dp[v][d[v]] += w[v];
    for (int j = 2; j <= k; j ++)
        dp[v][j] = max(dp[v][j], dp[v][j - 1]);
}

void solve()
{
    cin >> n >> m >> k;
    for (int i = 2; i <= n; i ++)
    {
        cin >> p[i];
        adj[p[i]].push_back(i);
    }
    for (int i = 1; i <= m; i ++)
    {
        int v;
        cin >> v >> d[v] >> w[v];
    }

    dfs(1);

    cout << dp[1][k] << endl;
}

int main()
{
    solve();
    return 0;
}

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 2660 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 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 Runtime error 93 ms 44788 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 4 ms 2900 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 106 ms 23896 KB Output is correct
2 Correct 115 ms 23952 KB Output is correct
3 Correct 91 ms 27932 KB Output is correct
4 Correct 76 ms 22496 KB Output is correct
5 Correct 94 ms 33340 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 2660 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 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 106 ms 23336 KB Output is correct
11 Correct 91 ms 23200 KB Output is correct
12 Correct 88 ms 27356 KB Output is correct
13 Correct 64 ms 21828 KB Output is correct
14 Correct 81 ms 32612 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1903 ms 7064 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 2660 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 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 4 ms 2900 KB Output isn't correct
11 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 2660 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 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 Runtime error 93 ms 44788 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -