oj.uz

Submission #413526

# Submission time Handle Problem Language Result Execution time Memory
413526 2021-05-28T20:05:04 Z nicolaalexandra Magic Tree (CEOI19_magictree) C++14
61 / 100
 740 ms 705328 KB 
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;

int v[DIM],cost[DIM],d[DIM],a[DIM],w[DIM];
long long dp[DIM][1010];
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 cautare_binara (int v[], int n, int val){
    int st = 1, dr = n;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (v[mid] == val)
            return mid;
        if (v[mid] < val)
            st = mid+1;
        else dr = mid-1;
    }
}

int main (){

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

    cin>>n>>m>>k;

    int ok2 = 1; /// cazul cu lant
    for (i=2;i<=n;i++){
        cin>>x;
        L[x].push_back(i);
        L[i].push_back(x);

        if (x != i-1)
            ok2 = 0;
    }

    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 (cost[x] != 1)
            ok2 = 0;
    }

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

    if (ok2){
        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;
    }

    /// normalizez v urii
    int el = 0;
    for (i=1;i<=n;i++)
        if (v[i])
            w[++el] = v[i];

    sort (w+1,w+el+1);

    int el2 = 1;
    for (i=2;i<=m;i++)
        if (w[i] != w[i-1])
            w[++el2] = w[i];
    el = el2;

    for (i=1;i<=n;i++){
        if (!v[i])
            continue;
        int val = v[i];
        v[i] = cautare_binara (w,el,val);
    }

    k = el;


    dfs (1,0);


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

    cout<<sol;



    return 0;
}

Compilation message

magictree.cpp: In function 'int cautare_binara(int*, int, int)':
magictree.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
   60 | }
      | ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2700 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 86 ms 6724 KB Output is correct
2 Correct 74 ms 5980 KB Output is correct
3 Correct 150 ms 6900 KB Output is correct
4 Correct 133 ms 6960 KB Output is correct
5 Correct 149 ms 6884 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 2636 KB Output is correct
4 Correct 129 ms 6856 KB Output is correct
5 Correct 143 ms 7236 KB Output is correct
6 Correct 138 ms 6840 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 389572 KB Output is correct
2 Correct 323 ms 388624 KB Output is correct
3 Correct 311 ms 404380 KB Output is correct
4 Correct 272 ms 369464 KB Output is correct
5 Correct 292 ms 416260 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2700 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 322 ms 399812 KB Output is correct
11 Correct 317 ms 394820 KB Output is correct
12 Correct 301 ms 417052 KB Output is correct
13 Correct 260 ms 375768 KB Output is correct
14 Correct 116 ms 6920 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 92868 KB Output is correct
2 Correct 515 ms 440528 KB Output is correct
3 Correct 513 ms 439944 KB Output is correct
4 Correct 588 ms 470592 KB Output is correct
5 Correct 205 ms 16696 KB Output is correct
6 Correct 528 ms 422244 KB Output is correct
7 Correct 740 ms 705328 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2700 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 2636 KB Output is correct
13 Correct 129 ms 6856 KB Output is correct
14 Correct 143 ms 7236 KB Output is correct
15 Correct 138 ms 6840 KB Output is correct
16 Correct 322 ms 399812 KB Output is correct
17 Correct 317 ms 394820 KB Output is correct
18 Correct 301 ms 417052 KB Output is correct
19 Correct 260 ms 375768 KB Output is correct
20 Correct 116 ms 6920 KB Output is correct
21 Incorrect 232 ms 157168 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 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2700 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 86 ms 6724 KB Output is correct
11 Correct 74 ms 5980 KB Output is correct
12 Correct 150 ms 6900 KB Output is correct
13 Correct 133 ms 6960 KB Output is correct
14 Correct 149 ms 6884 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 2636 KB Output is correct
18 Correct 129 ms 6856 KB Output is correct
19 Correct 143 ms 7236 KB Output is correct
20 Correct 138 ms 6840 KB Output is correct
21 Correct 365 ms 389572 KB Output is correct
22 Correct 323 ms 388624 KB Output is correct
23 Correct 311 ms 404380 KB Output is correct
24 Correct 272 ms 369464 KB Output is correct
25 Correct 292 ms 416260 KB Output is correct
26 Correct 322 ms 399812 KB Output is correct
27 Correct 317 ms 394820 KB Output is correct
28 Correct 301 ms 417052 KB Output is correct
29 Correct 260 ms 375768 KB Output is correct
30 Correct 116 ms 6920 KB Output is correct
31 Correct 108 ms 92868 KB Output is correct
32 Correct 515 ms 440528 KB Output is correct
33 Correct 513 ms 439944 KB Output is correct
34 Correct 588 ms 470592 KB Output is correct
35 Correct 205 ms 16696 KB Output is correct
36 Correct 528 ms 422244 KB Output is correct
37 Correct 740 ms 705328 KB Output is correct
38 Incorrect 232 ms 157168 KB Output isn't correct
39 Halted 0 ms 0 KB -