oj.uz

Submission #775742

# Submission time Handle Problem Language Result Execution time Memory
775742 2023-07-06T20:59:19 Z danikoynov Magic Tree (CEOI19_magictree) C++14
34 / 100
 2000 ms 75596 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], diff[maxn][maxk];
vector < int > adj[maxn];

void dfs(int v)
{
    for (int u : adj[v])
    {
        dfs(u);
        for (int j = 0; j <= k; j ++)
        {
            dp[v][j] += dp[u][j];
            diff[v][j] += diff[u][j];
        //for (int j = 2; j <= k; j ++)
        //dp[v][j] = max(dp[v][j], dp[v][j - 1]);
            /**int pt = j;
            ll sum = diff[v][j];
            while(sum < 0)
            {

            }*/
        }
    }


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

    for (int j = 2; j <= k; j ++)
        dp[v][j] = max(dp[v][j], dp[v][j - 1]);
    ///ll sum = 0;
    ///for (int j = 1)
        /**cout << "----------" << endl;
        cout << v << endl;
        for (int j = 1; j < k; j ++)
            cout << diff[v][j] << " ";
        cout << endl;*/
}

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);
    ll ans = 0;
    for (int j = 0; j < k; j ++)
        ans = ans + diff[1][j];
    cout  << ans << endl;
}

int main()
{
    solve();
    return 0;
}
/**
6 4 10
1
2
1
4
4
3 3 4
4 2 5
5 5 1
6 3 9
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 2644 KB Output is correct
5 Correct 2 ms 2656 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2664 KB Output is correct
8 Correct 1 ms 2660 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 115 ms 75596 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 3028 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 104 ms 38260 KB Output is correct
2 Correct 102 ms 38464 KB Output is correct
3 Correct 98 ms 42476 KB Output is correct
4 Correct 75 ms 37360 KB Output is correct
5 Correct 92 ms 47872 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 2644 KB Output is correct
5 Correct 2 ms 2656 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2664 KB Output is correct
8 Correct 1 ms 2660 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 107 ms 38448 KB Output is correct
11 Correct 109 ms 38628 KB Output is correct
12 Correct 99 ms 42504 KB Output is correct
13 Correct 83 ms 37408 KB Output is correct
14 Correct 83 ms 47780 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 10708 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 2644 KB Output is correct
5 Correct 2 ms 2656 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2664 KB Output is correct
8 Correct 1 ms 2660 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Incorrect 4 ms 3028 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 2644 KB Output is correct
5 Correct 2 ms 2656 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2664 KB Output is correct
8 Correct 1 ms 2660 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Runtime error 115 ms 75596 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -