oj.uz

Submission #413476

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

int dp[DIM][30],v[DIM],cost[DIM];
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]){
            int 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, 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);

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

    cout<<sol;

    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 6584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 18300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2648 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 2636 KB Output is correct
10 Correct 160 ms 18392 KB Output is correct
11 Correct 145 ms 19824 KB Output is correct
12 Correct 145 ms 22236 KB Output is correct
13 Correct 115 ms 19744 KB Output is correct
14 Correct 129 ms 25940 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2648 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 2636 KB Output is correct
10 Incorrect 7 ms 2764 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2648 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 2636 KB Output is correct
10 Incorrect 87 ms 6584 KB Output isn't correct
11 Halted 0 ms 0 KB -