oj.uz

Submission #775744

# Submission time Handle Problem Language Result Execution time Memory
775744 2023-07-06T21:02:47 Z danikoynov Magic Tree (CEOI19_magictree) C++14
34 / 100
 2000 ms 31092 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 ++)
            diff[v][j] += diff[u][j];
    }



    if (d[v] != 0)
    {
        diff[v][d[v] - 1] += w[v];
        diff[v][d[v]] -= w[v];
        int pt = d[v];
        while(pt < k)
        {
            if (diff[v][pt] < 0)
            {
                diff[v][pt + 1] += diff[v][pt];
                diff[v][pt] = 0;
                pt ++;
            }
            else
            {
                break;
            }
        }
    }
    /**for (int j = 0; j < k; j ++)
    {
        if (diff[v][j] < 0)
        {
            diff[v][j + 1] += diff[v][j];
            diff[v][j] = 0;
        }
    }*/
}

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 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 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 91 ms 21792 KB Output is correct
2 Correct 90 ms 21868 KB Output is correct
3 Correct 94 ms 25892 KB Output is correct
4 Correct 69 ms 20672 KB Output is correct
5 Correct 90 ms 31088 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 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 87 ms 21804 KB Output is correct
11 Correct 84 ms 21824 KB Output is correct
12 Correct 81 ms 25768 KB Output is correct
13 Correct 59 ms 20736 KB Output is correct
14 Correct 76 ms 31092 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 547 ms 6940 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 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Incorrect 2 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 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Execution timed out 2078 ms 22448 KB Time limit exceeded
11 Halted 0 ms 0 KB -