oj.uz

Submission #413506

# Submission time Handle Problem Language Result Execution time Memory
413506 2021-05-28T19:40:35 Z nicolaalexandra Magic Tree (CEOI19_magictree) C++14
37 / 100
 2000 ms 38408 KB 
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;

int v[DIM],cost[DIM];
long long dp[DIM][30];
vector <int> L[DIM];
int n,m,k,i,j,x,y,w,d;

void dfs (int nod, int tata){

    int ok = 0;
    for (auto vecin : L[nod])
        if (vecin != tata){
            ok = 1;
            dfs (vecin,nod);
        }

    if (!ok){
        if (v[nod]){
            for (int i=v[nod];i<=k;i++)
                dp[nod][i] = cost[nod];
        }

    } else {


        for (auto vecin : L[nod]){
            if (vecin == tata)
                continue;
            for (int i=1;i<=k;i++){
                dp[nod][i] += dp[vecin][i];
            }
        }

        if (v[nod]){
            long long val = cost[nod];
            for (auto vecin : L[nod])
                if (vecin != tata)
                    val += dp[vecin][v[nod]];
            dp[nod][v[nod]] = max (dp[nod][v[nod]],val);
        }

        for (int i=1;i<=k;i++)
            dp[nod][i] = max (dp[nod][i],dp[nod][i-1]);
    }

}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m>>k;
    for (i=2;i<=n;i++){
        cin>>x;
        L[x].push_back(i);
        L[i].push_back(x);
    }

    int ok = 1; long long sum = 0;
    for (i=1;i<=m;i++){
        cin>>x>>d>>w;
        v[x] = d, cost[x] = w;

        if (L[x].size() > 1)
            ok = 0;
        sum += w;
    }

    if (ok){
        cout<<sum;
        return 0;
    }

    dfs (1,0);


    long long sol = 0;
    for (i=1;i<=k;i++)
        sol = max (sol,dp[1][i]);

    /*for (i=1;i<=n;i++,cout<<"\n")
        for (j=1;j<=k;j++)
            cout<<dp[i][j]<<" ";
*/
    cout<<sol;

    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2596 KB Output is correct
3 Correct 3 ms 2764 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2656 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 7748 KB Output is correct
2 Correct 81 ms 6860 KB Output is correct
3 Correct 154 ms 9388 KB Output is correct
4 Correct 131 ms 9056 KB Output is correct
5 Correct 150 ms 9336 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 2892 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 178 ms 32208 KB Output is correct
2 Correct 206 ms 32240 KB Output is correct
3 Correct 172 ms 34620 KB Output is correct
4 Correct 140 ms 32156 KB Output is correct
5 Correct 149 ms 38408 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2596 KB Output is correct
3 Correct 3 ms 2764 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2656 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 175 ms 31544 KB Output is correct
11 Correct 158 ms 31500 KB Output is correct
12 Correct 144 ms 33988 KB Output is correct
13 Correct 115 ms 31508 KB Output is correct
14 Correct 134 ms 37756 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2596 KB Output is correct
3 Correct 3 ms 2764 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2656 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Incorrect 10 ms 2892 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 2764 KB Output is correct
2 Correct 2 ms 2596 KB Output is correct
3 Correct 3 ms 2764 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2656 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 80 ms 7748 KB Output is correct
11 Correct 81 ms 6860 KB Output is correct
12 Correct 154 ms 9388 KB Output is correct
13 Correct 131 ms 9056 KB Output is correct
14 Correct 150 ms 9336 KB Output is correct
15 Incorrect 10 ms 2892 KB Output isn't correct
16 Halted 0 ms 0 KB -