oj.uz

Submission #582591

# Submission time Handle Problem Language Result Execution time Memory
582591 2022-06-24T06:45:45 Z 박상훈(#8369) Magic Tree (CEOI19_magictree) C++17
11 / 100
 97 ms 9860 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Seg{
    vector<ll> tree, a;
    int sz;
    void init() {
        a.push_back(0); ///dummy node
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end()); /// a -> possible time
        sz = a.size();
        tree.clear(); tree.resize(sz*4, 0);
    }
    void update(int i, int l, int r, int s, ll x){
        //propagate(i, l, r);
        if (r<s || s<l) return;
        if (l==r){
            tree[i] = max(tree[i], x);
            return;
        }
        int m = (l+r)>>1;
        update(i<<1, l, m, s, x); update(i<<1|1, m+1, r, s, x);
        tree[i] = max(tree[i<<1], tree[i<<1|1]);
    }
    ll query(int i, int l, int r, int s, int e){
        //propagate(i, l, r);
        if (r<s || e<l) return 0;
        if (s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return max(query(i<<1, l, m, s, e), query(i<<1|1, m+1, r, s, e));
    }

    int getidx(int t){return lower_bound(a.begin(), a.end(), t) - a.begin();}
    void update(int t, ll x){
        int idx = getidx(t);
        update(1, 0, sz-1, idx, x);
    }
    ll query(int tl, int tr){
        int idxl = getidx(tl), idxr = getidx(tr);
        return query(1, 0, sz-1, idxl, idxr);
    }
}tree;

vector<int> G[100100];
int par[100100], D[100100], W[100100];

int main(){
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    par[1] = -1;

    for (int i=2;i<=n;i++){
        scanf("%d", par+i);
        G[par[i]].push_back(i);
    }

    for (int i=1;i<=m;i++){
        int v, d, w;
        scanf("%d %d %d", &v, &d, &w);
        D[v] = d, W[v] = w;
        tree.a.push_back(d);
    }

    tree.init();

    for (int i=n;i>=2;i--) if (D[i]){
        ll prv = tree.query(0, D[i]);
        tree.update(D[i], W[i] + prv);
    }

    printf("%lld\n", tree.tree[1]);
    return 0;
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%d", par+i);
      |         ~~~~~^~~~~~~~~~~~~
magictree.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d %d %d", &v, &d, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 6196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 77 ms 9860 KB Output is correct
5 Correct 71 ms 9848 KB Output is correct
6 Correct 97 ms 9848 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 6568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -