oj.uz

Submission #582612

# Submission time Handle Problem Language Result Execution time Memory
582612 2022-06-24T07:29:27 Z 박상훈(#8369) Magic Tree (CEOI19_magictree) C++17
45 / 100
 517 ms 55024 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 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){
        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);
    }
}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, e = 0, mx = 0;
    for (auto &t:tree[B].a){
        ll y1 = tree[B].query(t, t);

        if (mx < y1){
            tree[A].update2(s, e, mx);
            mx = y1;
            s = t;
        }
        e = 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(t, 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);
    }
    if (D[s]){
        ll prv = tree[top[s]].query(0, D[s]);
        tree[top[s]].update(D[s], prv + W[s]);
    }

    /*printf("Vertex %d / Seg %d\n", s, top[s]);
    for (auto &t:tree[top[s]].a){
        printf("%lld -> %lld\n", t, tree[top[s]].query(t, 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:157:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |     scanf("%lld %lld %lld", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:161:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         scanf("%lld", par+i);
      |         ~~~~~^~~~~~~~~~~~~~~
magictree.cpp:167:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         scanf("%lld %lld %lld", &v, &d, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 32600 KB Output is correct
2 Correct 122 ms 26716 KB Output is correct
3 Correct 517 ms 55024 KB Output is correct
4 Correct 300 ms 37768 KB Output is correct
5 Correct 356 ms 38068 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 6 ms 10736 KB Output is correct
3 Correct 7 ms 10708 KB Output is correct
4 Correct 146 ms 34816 KB Output is correct
5 Correct 113 ms 34924 KB Output is correct
6 Correct 145 ms 34912 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 30432 KB Output is correct
2 Correct 193 ms 29504 KB Output is correct
3 Correct 118 ms 26564 KB Output is correct
4 Correct 104 ms 33976 KB Output is correct
5 Correct 68 ms 30816 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 5 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10424 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 8 ms 10452 KB Output is correct
10 Incorrect 285 ms 34472 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13140 KB Output is correct
2 Correct 83 ms 22644 KB Output is correct
3 Correct 104 ms 22728 KB Output is correct
4 Correct 102 ms 22768 KB Output is correct
5 Correct 70 ms 27752 KB Output is correct
6 Correct 91 ms 26160 KB Output is correct
7 Correct 71 ms 24548 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 5 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10424 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 8 ms 10452 KB Output is correct
10 Correct 7 ms 10708 KB Output is correct
11 Correct 6 ms 10736 KB Output is correct
12 Correct 7 ms 10708 KB Output is correct
13 Correct 146 ms 34816 KB Output is correct
14 Correct 113 ms 34924 KB Output is correct
15 Correct 145 ms 34912 KB Output is correct
16 Incorrect 285 ms 34472 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 5 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10424 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 8 ms 10452 KB Output is correct
10 Correct 194 ms 32600 KB Output is correct
11 Correct 122 ms 26716 KB Output is correct
12 Correct 517 ms 55024 KB Output is correct
13 Correct 300 ms 37768 KB Output is correct
14 Correct 356 ms 38068 KB Output is correct
15 Correct 7 ms 10708 KB Output is correct
16 Correct 6 ms 10736 KB Output is correct
17 Correct 7 ms 10708 KB Output is correct
18 Correct 146 ms 34816 KB Output is correct
19 Correct 113 ms 34924 KB Output is correct
20 Correct 145 ms 34912 KB Output is correct
21 Correct 166 ms 30432 KB Output is correct
22 Correct 193 ms 29504 KB Output is correct
23 Correct 118 ms 26564 KB Output is correct
24 Correct 104 ms 33976 KB Output is correct
25 Correct 68 ms 30816 KB Output is correct
26 Incorrect 285 ms 34472 KB Output isn't correct
27 Halted 0 ms 0 KB -