oj.uz

Submission #413518

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

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

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;
        cin>>v[x]>>cost[x];

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

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


    /// cazul cand e lant
    ok = 1;
    for (i=2;i<n;i++)
        if (L[i].size() != 2){
            ok = 0;
            break;
        }

    if (ok){
        int el = 0;
        for (i=1;i<=n;i++)
            if (v[i])
                a[++el] = v[i];
        reverse (a+1,a+el+1);
        int sz = 0;
        for (i=1;i<=el;i++){
            int st = 1, dr = sz;
            while (st <= dr){
                int mid = (st+dr)>>1;
                if (a[d[mid]] <= a[i])
                    st = mid+1;
                else dr = mid-1;
            }
            if (st == sz+1)
                sz++;
            d[st] = i;
        }

        cout<<sz;


        return 0;
    }


    dfs (1,0);


    long long 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 2 ms 2636 KB Output is correct
2 Correct 4 ms 2644 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 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 2636 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 79 ms 6768 KB Output is correct
2 Correct 69 ms 6852 KB Output is correct
3 Correct 185 ms 9388 KB Output is correct
4 Correct 151 ms 8968 KB Output is correct
5 Correct 143 ms 9280 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 133 ms 8908 KB Output is correct
5 Correct 139 ms 9204 KB Output is correct
6 Correct 154 ms 8868 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 30200 KB Output is correct
2 Correct 163 ms 32248 KB Output is correct
3 Correct 176 ms 34664 KB Output is correct
4 Correct 131 ms 32096 KB Output is correct
5 Incorrect 137 ms 9172 KB Output isn't correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 4 ms 2644 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 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 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 190 ms 30156 KB Output is correct
11 Correct 192 ms 30200 KB Output is correct
12 Correct 145 ms 32580 KB Output is correct
13 Correct 115 ms 30452 KB Output is correct
14 Correct 124 ms 6992 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 8660 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 2636 KB Output is correct
2 Correct 4 ms 2644 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 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 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 3 ms 2652 KB Output is correct
13 Correct 133 ms 8908 KB Output is correct
14 Correct 139 ms 9204 KB Output is correct
15 Correct 154 ms 8868 KB Output is correct
16 Correct 190 ms 30156 KB Output is correct
17 Correct 192 ms 30200 KB Output is correct
18 Correct 145 ms 32580 KB Output is correct
19 Correct 115 ms 30452 KB Output is correct
20 Correct 124 ms 6992 KB Output is correct
21 Incorrect 156 ms 8464 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 4 ms 2644 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 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 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 79 ms 6768 KB Output is correct
11 Correct 69 ms 6852 KB Output is correct
12 Correct 185 ms 9388 KB Output is correct
13 Correct 151 ms 8968 KB Output is correct
14 Correct 143 ms 9280 KB Output is correct
15 Correct 3 ms 2636 KB Output is correct
16 Correct 3 ms 2636 KB Output is correct
17 Correct 3 ms 2652 KB Output is correct
18 Correct 133 ms 8908 KB Output is correct
19 Correct 139 ms 9204 KB Output is correct
20 Correct 154 ms 8868 KB Output is correct
21 Correct 170 ms 30200 KB Output is correct
22 Correct 163 ms 32248 KB Output is correct
23 Correct 176 ms 34664 KB Output is correct
24 Correct 131 ms 32096 KB Output is correct
25 Incorrect 137 ms 9172 KB Output isn't correct