oj.uz

Submission #413806

# Submission time Handle Problem Language Result Execution time Memory
413806 2021-05-29T14:06:47 Z nicolaalexandra Magic Tree (CEOI19_magictree) C++14
48 / 100
 2000 ms 29316 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];
set <pair<int,long long> > s[DIM];
set <int> aux;
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])
            s[nod].insert(make_pair(v[nod],cost[nod]));

    } else {

        /// toti timpii ditincti
        aux.clear();
        for (auto vecin : L[nod]){
            if (vecin == tata)
                continue;
            for (auto it : s[vecin]){
                s[nod].insert(make_pair(it.first,0LL));
                aux.insert(it.first);
            }
        }

        for (auto timp : aux){

            for (auto vecin : L[nod]){
                if (vecin == tata || s[vecin].empty())
                    continue;

                set <pair<int,long long> > :: iterator it2 = s[vecin].lower_bound(make_pair(timp,0));
                if (it2 == s[vecin].end())
                    it2--;
                if (it2 != s[vecin].begin() && it2->first > timp)
                    it2--;
                if (it2->first <= timp){


                    set <pair<int,long long> > :: iterator it3 = s[nod].lower_bound(make_pair(timp,0));
                    long long val = it3->second + it2->second;

                    s[nod].erase(it3);
                    s[nod].insert(make_pair(timp,val));
                }
            }

        }

        if (v[nod]){
            /// dp[nod][d]

            if (aux.empty()){
                s[nod].insert(make_pair(v[nod],cost[nod]));
            } else {

                set <pair<int,long long> > :: iterator it = s[nod].lower_bound(make_pair(v[nod],0));
                if (it == s[nod].end())
                    it--;
                if (it != s[nod].begin() && it->first > v[nod])
                    it--;

                long long val = cost[nod];
                if (it->first <= v[nod])
                    val += it->second;

                if (it->first == v[nod])
                    s[nod].erase(it);

                s[nod].insert(make_pair(v[nod],val));


                for (auto it : aux)
                    if (it >= v[nod]){
                        set <pair<int,long long> > :: iterator it2 = s[nod].lower_bound(make_pair(it,0));
                        long long nr = max (it2->second,val);

                        if (nr > it2->second){
                            s[nod].erase(it2);
                            s[nod].insert(make_pair(it,nr));
                        }
                    }
            }
        }

        for (auto vecin : L[nod])
            if (vecin != tata)
                s[vecin].clear();

    }

}

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 (auto it : s[1])
        sol = max (sol,it.second);

    cout<<sol;



    return 0;
}

Compilation message

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

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 11440 KB Output is correct
2 Correct 70 ms 10540 KB Output is correct
3 Correct 144 ms 11600 KB Output is correct
4 Correct 131 ms 11648 KB Output is correct
5 Correct 150 ms 11624 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7396 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 6 ms 7404 KB Output is correct
4 Correct 138 ms 11744 KB Output is correct
5 Correct 134 ms 12008 KB Output is correct
6 Correct 152 ms 11524 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 11716 KB Output is correct
2 Correct 194 ms 13796 KB Output is correct
3 Correct 231 ms 20012 KB Output is correct
4 Correct 153 ms 19388 KB Output is correct
5 Correct 183 ms 29316 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 5 ms 7244 KB Output is correct
4 Correct 5 ms 7320 KB Output is correct
5 Correct 6 ms 7244 KB Output is correct
6 Correct 4 ms 7244 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 5 ms 7244 KB Output is correct
9 Correct 5 ms 7244 KB Output is correct
10 Correct 275 ms 11636 KB Output is correct
11 Correct 259 ms 11616 KB Output is correct
12 Correct 564 ms 17872 KB Output is correct
13 Correct 198 ms 17540 KB Output is correct
14 Correct 119 ms 11540 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8268 KB Output is correct
2 Correct 77 ms 11416 KB Output is correct
3 Correct 98 ms 11492 KB Output is correct
4 Correct 86 ms 11608 KB Output is correct
5 Correct 365 ms 12072 KB Output is correct
6 Execution timed out 2062 ms 15416 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 5 ms 7244 KB Output is correct
4 Correct 5 ms 7320 KB Output is correct
5 Correct 6 ms 7244 KB Output is correct
6 Correct 4 ms 7244 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 5 ms 7244 KB Output is correct
9 Correct 5 ms 7244 KB Output is correct
10 Correct 6 ms 7396 KB Output is correct
11 Correct 5 ms 7372 KB Output is correct
12 Correct 6 ms 7404 KB Output is correct
13 Correct 138 ms 11744 KB Output is correct
14 Correct 134 ms 12008 KB Output is correct
15 Correct 152 ms 11524 KB Output is correct
16 Correct 275 ms 11636 KB Output is correct
17 Correct 259 ms 11616 KB Output is correct
18 Correct 564 ms 17872 KB Output is correct
19 Correct 198 ms 17540 KB Output is correct
20 Correct 119 ms 11540 KB Output is correct
21 Correct 171 ms 8780 KB Output is correct
22 Correct 477 ms 12312 KB Output is correct
23 Correct 941 ms 17976 KB Output is correct
24 Correct 1640 ms 22748 KB Output is correct
25 Execution timed out 2078 ms 24184 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 5 ms 7244 KB Output is correct
4 Correct 5 ms 7320 KB Output is correct
5 Correct 6 ms 7244 KB Output is correct
6 Correct 4 ms 7244 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 5 ms 7244 KB Output is correct
9 Correct 5 ms 7244 KB Output is correct
10 Correct 83 ms 11440 KB Output is correct
11 Correct 70 ms 10540 KB Output is correct
12 Correct 144 ms 11600 KB Output is correct
13 Correct 131 ms 11648 KB Output is correct
14 Correct 150 ms 11624 KB Output is correct
15 Correct 6 ms 7396 KB Output is correct
16 Correct 5 ms 7372 KB Output is correct
17 Correct 6 ms 7404 KB Output is correct
18 Correct 138 ms 11744 KB Output is correct
19 Correct 134 ms 12008 KB Output is correct
20 Correct 152 ms 11524 KB Output is correct
21 Correct 199 ms 11716 KB Output is correct
22 Correct 194 ms 13796 KB Output is correct
23 Correct 231 ms 20012 KB Output is correct
24 Correct 153 ms 19388 KB Output is correct
25 Correct 183 ms 29316 KB Output is correct
26 Correct 275 ms 11636 KB Output is correct
27 Correct 259 ms 11616 KB Output is correct
28 Correct 564 ms 17872 KB Output is correct
29 Correct 198 ms 17540 KB Output is correct
30 Correct 119 ms 11540 KB Output is correct
31 Correct 22 ms 8268 KB Output is correct
32 Correct 77 ms 11416 KB Output is correct
33 Correct 98 ms 11492 KB Output is correct
34 Correct 86 ms 11608 KB Output is correct
35 Correct 365 ms 12072 KB Output is correct
36 Execution timed out 2062 ms 15416 KB Time limit exceeded
37 Halted 0 ms 0 KB -