oj.uz

Submission #582674

# Submission time Handle Problem Language Result Execution time Memory
582674 2022-06-24T08:43:57 Z 박상훈(#8369) Magic Tree (CEOI19_magictree) C++17
100 / 100
 630 ms 55216 KB 
#include <bits/stdc++.h>
#define int long long

typedef long long ll;
using namespace std;
struct Seg{
    vector<ll> tree, a, lazy;
    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);
        lazy.clear(); lazy.resize(sz*4, 0);
    }
    void propagate(int i, int l, int r){
        tree[i] += lazy[i];
        if (l!=r){
            lazy[i<<1] += lazy[i];
            lazy[i<<1|1] += lazy[i];
        }
        lazy[i] = 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));
    }
    void update2(int i, int l, int r, int s, int e, ll x){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] += x;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update2(i<<1, l, m, s, e, x); update2(i<<1|1, m+1, r, s, e, x);
        tree[i] = max(tree[i<<1], tree[i<<1|1]);
    }


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

        int idxl = getidx(tl), idxr = getidx(tr);
        return query(1, 0, sz-1, idxl, idxr);
    }
    void update2(int tl, int tr, ll x){
        int idxl = getidx(tl), idxr = getidx(tr);
        update2(1, 0, sz-1, idxl, idxr, x);
    }
    void clear(){
        tree.clear(); lazy.clear(); a.clear();
        sz = 0;
    }
}tree[100100];

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

void dfs1(int s){
    sz[s] = 1;
    for (auto &v:G[s]){
        dfs1(v);
        sz[s] += sz[v];
        if (sz[v] > sz[G[s][0]]) swap(v, G[s][0]);
    }
}

void dfs2(int s){
    for (auto &v:G[s]){
        if (v==G[s][0]) top[v] = top[s];
        else top[v] = v;
        dfs2(v);
    }
}

void dfs3(int s, int r){
    if (D[s]) tree[r].a.push_back(D[s]);
    for (auto &v:G[s]) dfs3(v, r);
}

void build(int s){
    dfs3(s, s);
    tree[s].init();
}

void _merge(int A, int B){ ///A <- B
    vector<ll> X;
    for (auto &t:tree[B].a){
        X.push_back(tree[A].query(0, t));
    }
    reverse(X.begin(), X.end());

    ///case 1 (B -> A)
    ll s = 0, mx = 0;
    for (auto &t:tree[B].a){
        ll y1 = tree[B].query(0, t);

        if (mx < y1){
            //printf("Merge %lld <- %lld / %lld ~ %lld += %lld\n", A, B, s, e, mx);
            tree[A].update2(s, t-1, mx);
            mx = y1;
            s = t;
        }
    }

    tree[A].update2(s, tree[A].a.back(), mx);

    ///case 2 (A -> B)
    for (auto &t:tree[B].a){
        ll x2 = X.back(); X.pop_back();
        ll y2 = tree[B].query(0, t);
        //printf(" %d %d , time %lld -> %lld %lld\n", A, B, t, x2, y2);
        tree[A].update(t, x2 + y2);
    }
}

void dfs(int s){
    for (auto &v:G[s]){
        dfs(v);
        if (v!=G[s][0]) _merge(top[s], v);

        assert(top[G[s][0]]==top[s]);
        if (v!=G[s][0]) assert(top[v]==v);
    }
    if (D[s]){
        ll prv = tree[top[s]].query(0, D[s]);
        tree[top[s]].update(D[s], prv + W[s]);
    }

    /*printf("Vertex %lld / Seg %lld\n", s, top[s]);
    for (auto &t:tree[top[s]].a){
        printf("%lld -> %lld\n", t, tree[top[s]].query(0, t));
    }
    printf("\n");*/
}


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

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

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

    top[1] = 1;
    dfs1(1);
    dfs2(1);
    for (int i=1;i<=n;i++) if (top[i]==i) build(i);

    /*for (int i=1;i<=n;i++) printf("%d ", top[i]);
    printf("\n");*/

    dfs(1); ///calc ans
    printf("%lld\n", tree[1].query(-1, -1));

    return 0;
}


/*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]);*/

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10516 KB Output is correct
2 Correct 8 ms 10428 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10520 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 6 ms 10452 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 32568 KB Output is correct
2 Correct 129 ms 25936 KB Output is correct
3 Correct 530 ms 55216 KB Output is correct
4 Correct 347 ms 37772 KB Output is correct
5 Correct 356 ms 37908 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10708 KB Output is correct
2 Correct 9 ms 10708 KB Output is correct
3 Correct 7 ms 10708 KB Output is correct
4 Correct 127 ms 33360 KB Output is correct
5 Correct 106 ms 33360 KB Output is correct
6 Correct 134 ms 33352 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 30420 KB Output is correct
2 Correct 181 ms 29536 KB Output is correct
3 Correct 111 ms 26048 KB Output is correct
4 Correct 102 ms 33980 KB Output is correct
5 Correct 62 ms 29280 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10516 KB Output is correct
2 Correct 8 ms 10428 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10520 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 6 ms 10452 KB Output is correct
10 Correct 236 ms 34548 KB Output is correct
11 Correct 208 ms 33136 KB Output is correct
12 Correct 109 ms 26092 KB Output is correct
13 Correct 130 ms 34044 KB Output is correct
14 Correct 84 ms 29236 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 13140 KB Output is correct
2 Correct 101 ms 22732 KB Output is correct
3 Correct 116 ms 22732 KB Output is correct
4 Correct 109 ms 22800 KB Output is correct
5 Correct 90 ms 27828 KB Output is correct
6 Correct 96 ms 25804 KB Output is correct
7 Correct 60 ms 23880 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10516 KB Output is correct
2 Correct 8 ms 10428 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10520 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 6 ms 10452 KB Output is correct
10 Correct 7 ms 10708 KB Output is correct
11 Correct 9 ms 10708 KB Output is correct
12 Correct 7 ms 10708 KB Output is correct
13 Correct 127 ms 33360 KB Output is correct
14 Correct 106 ms 33360 KB Output is correct
15 Correct 134 ms 33352 KB Output is correct
16 Correct 236 ms 34548 KB Output is correct
17 Correct 208 ms 33136 KB Output is correct
18 Correct 109 ms 26092 KB Output is correct
19 Correct 130 ms 34044 KB Output is correct
20 Correct 84 ms 29236 KB Output is correct
21 Correct 79 ms 17040 KB Output is correct
22 Correct 336 ms 34372 KB Output is correct
23 Correct 331 ms 38948 KB Output is correct
24 Correct 630 ms 52608 KB Output is correct
25 Correct 294 ms 37640 KB Output is correct
26 Correct 341 ms 36944 KB Output is correct
27 Correct 247 ms 34596 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10516 KB Output is correct
2 Correct 8 ms 10428 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10520 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 6 ms 10452 KB Output is correct
10 Correct 236 ms 32568 KB Output is correct
11 Correct 129 ms 25936 KB Output is correct
12 Correct 530 ms 55216 KB Output is correct
13 Correct 347 ms 37772 KB Output is correct
14 Correct 356 ms 37908 KB Output is correct
15 Correct 7 ms 10708 KB Output is correct
16 Correct 9 ms 10708 KB Output is correct
17 Correct 7 ms 10708 KB Output is correct
18 Correct 127 ms 33360 KB Output is correct
19 Correct 106 ms 33360 KB Output is correct
20 Correct 134 ms 33352 KB Output is correct
21 Correct 149 ms 30420 KB Output is correct
22 Correct 181 ms 29536 KB Output is correct
23 Correct 111 ms 26048 KB Output is correct
24 Correct 102 ms 33980 KB Output is correct
25 Correct 62 ms 29280 KB Output is correct
26 Correct 236 ms 34548 KB Output is correct
27 Correct 208 ms 33136 KB Output is correct
28 Correct 109 ms 26092 KB Output is correct
29 Correct 130 ms 34044 KB Output is correct
30 Correct 84 ms 29236 KB Output is correct
31 Correct 24 ms 13140 KB Output is correct
32 Correct 101 ms 22732 KB Output is correct
33 Correct 116 ms 22732 KB Output is correct
34 Correct 109 ms 22800 KB Output is correct
35 Correct 90 ms 27828 KB Output is correct
36 Correct 96 ms 25804 KB Output is correct
37 Correct 60 ms 23880 KB Output is correct
38 Correct 79 ms 17040 KB Output is correct
39 Correct 336 ms 34372 KB Output is correct
40 Correct 331 ms 38948 KB Output is correct
41 Correct 630 ms 52608 KB Output is correct
42 Correct 294 ms 37640 KB Output is correct
43 Correct 341 ms 36944 KB Output is correct
44 Correct 247 ms 34596 KB Output is correct
45 Correct 85 ms 17460 KB Output is correct
46 Correct 292 ms 35904 KB Output is correct
47 Correct 414 ms 40200 KB Output is correct
48 Correct 577 ms 54972 KB Output is correct
49 Correct 313 ms 39972 KB Output is correct
50 Correct 369 ms 39488 KB Output is correct
51 Correct 235 ms 35292 KB Output is correct