oj.uz

Submission #413785

# Submission time Handle Problem Language Result Execution time Memory
413785 2021-05-29T13:28:48 Z nicolaalexandra Magic Tree (CEOI19_magictree) C++14
36 / 100
 2000 ms 25532 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]));
            //for (int i=v[nod];i<=k;i++)
              //  dp[nod][i] = 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].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));
                        int 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:117:1: warning: control reaches end of non-void function [-Wreturn-type]
  117 | }
      | ^

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 12472 KB Output is correct
2 Correct 71 ms 11588 KB Output is correct
3 Correct 146 ms 14244 KB Output is correct
4 Correct 132 ms 13736 KB Output is correct
5 Correct 153 ms 14008 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7416 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7356 KB Output is correct
4 Correct 130 ms 13508 KB Output is correct
5 Correct 140 ms 13908 KB Output is correct
6 Correct 135 ms 13500 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 189 ms 13764 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 5 ms 7244 KB Output is correct
2 Correct 5 ms 7344 KB Output is correct
3 Correct 5 ms 7244 KB Output is correct
4 Correct 5 ms 7348 KB Output is correct
5 Correct 6 ms 7352 KB Output is correct
6 Correct 5 ms 7276 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 6 ms 7272 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 277 ms 13392 KB Output is correct
11 Correct 223 ms 13064 KB Output is correct
12 Correct 567 ms 19360 KB Output is correct
13 Correct 185 ms 18708 KB Output is correct
14 Correct 117 ms 13044 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 8332 KB Output is correct
2 Correct 77 ms 11956 KB Output is correct
3 Correct 90 ms 11960 KB Output is correct
4 Incorrect 78 ms 12076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 5 ms 7344 KB Output is correct
3 Correct 5 ms 7244 KB Output is correct
4 Correct 5 ms 7348 KB Output is correct
5 Correct 6 ms 7352 KB Output is correct
6 Correct 5 ms 7276 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 6 ms 7272 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 5 ms 7416 KB Output is correct
11 Correct 5 ms 7372 KB Output is correct
12 Correct 5 ms 7356 KB Output is correct
13 Correct 130 ms 13508 KB Output is correct
14 Correct 140 ms 13908 KB Output is correct
15 Correct 135 ms 13500 KB Output is correct
16 Correct 277 ms 13392 KB Output is correct
17 Correct 223 ms 13064 KB Output is correct
18 Correct 567 ms 19360 KB Output is correct
19 Correct 185 ms 18708 KB Output is correct
20 Correct 117 ms 13044 KB Output is correct
21 Correct 160 ms 9088 KB Output is correct
22 Correct 468 ms 13524 KB Output is correct
23 Correct 838 ms 19268 KB Output is correct
24 Correct 1595 ms 24404 KB Output is correct
25 Execution timed out 2070 ms 25532 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 5 ms 7344 KB Output is correct
3 Correct 5 ms 7244 KB Output is correct
4 Correct 5 ms 7348 KB Output is correct
5 Correct 6 ms 7352 KB Output is correct
6 Correct 5 ms 7276 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 6 ms 7272 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 82 ms 12472 KB Output is correct
11 Correct 71 ms 11588 KB Output is correct
12 Correct 146 ms 14244 KB Output is correct
13 Correct 132 ms 13736 KB Output is correct
14 Correct 153 ms 14008 KB Output is correct
15 Correct 5 ms 7416 KB Output is correct
16 Correct 5 ms 7372 KB Output is correct
17 Correct 5 ms 7356 KB Output is correct
18 Correct 130 ms 13508 KB Output is correct
19 Correct 140 ms 13908 KB Output is correct
20 Correct 135 ms 13500 KB Output is correct
21 Incorrect 189 ms 13764 KB Output isn't correct
22 Halted 0 ms 0 KB -