oj.uz

Submission #413523

# Submission time Handle Problem Language Result Execution time Memory
413523 2021-05-28T19:58:20 Z nicolaalexandra Magic Tree (CEOI19_magictree) C++14
48 / 100
 194 ms 36608 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][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 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 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 6596 KB Output is correct
2 Correct 72 ms 5908 KB Output is correct
3 Correct 164 ms 6996 KB Output is correct
4 Correct 134 ms 6952 KB Output is correct
5 Correct 147 ms 6920 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2640 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 134 ms 7000 KB Output is correct
5 Correct 131 ms 7244 KB Output is correct
6 Correct 137 ms 6912 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 30456 KB Output is correct
2 Correct 176 ms 30452 KB Output is correct
3 Correct 169 ms 32788 KB Output is correct
4 Correct 138 ms 30780 KB Output is correct
5 Correct 151 ms 36608 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 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 167 ms 30532 KB Output is correct
11 Correct 154 ms 30404 KB Output is correct
12 Correct 147 ms 32800 KB Output is correct
13 Correct 115 ms 30776 KB Output is correct
14 Correct 118 ms 6912 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 8048 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 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 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 2640 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 3 ms 2636 KB Output is correct
13 Correct 134 ms 7000 KB Output is correct
14 Correct 131 ms 7244 KB Output is correct
15 Correct 137 ms 6912 KB Output is correct
16 Correct 167 ms 30532 KB Output is correct
17 Correct 154 ms 30404 KB Output is correct
18 Correct 147 ms 32800 KB Output is correct
19 Correct 115 ms 30776 KB Output is correct
20 Correct 118 ms 6912 KB Output is correct
21 Incorrect 145 ms 8216 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 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 6596 KB Output is correct
11 Correct 72 ms 5908 KB Output is correct
12 Correct 164 ms 6996 KB Output is correct
13 Correct 134 ms 6952 KB Output is correct
14 Correct 147 ms 6920 KB Output is correct
15 Correct 3 ms 2640 KB Output is correct
16 Correct 3 ms 2636 KB Output is correct
17 Correct 3 ms 2636 KB Output is correct
18 Correct 134 ms 7000 KB Output is correct
19 Correct 131 ms 7244 KB Output is correct
20 Correct 137 ms 6912 KB Output is correct
21 Correct 194 ms 30456 KB Output is correct
22 Correct 176 ms 30452 KB Output is correct
23 Correct 169 ms 32788 KB Output is correct
24 Correct 138 ms 30780 KB Output is correct
25 Correct 151 ms 36608 KB Output is correct
26 Correct 167 ms 30532 KB Output is correct
27 Correct 154 ms 30404 KB Output is correct
28 Correct 147 ms 32800 KB Output is correct
29 Correct 115 ms 30776 KB Output is correct
30 Correct 118 ms 6912 KB Output is correct
31 Incorrect 58 ms 8048 KB Output isn't correct
32 Halted 0 ms 0 KB -