oj.uz

Submission #582604

# Submission time Handle Problem Language Result Execution time Memory
582604 2022-06-24T07:25:23 Z 박상훈(#8369) Magic Tree (CEOI19_magictree) C++17
17 / 100
 249 ms 32188 KB 
#include <bits/stdc++.h>

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)
    int 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");*/
}


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;
    }

    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:156:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:160:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         scanf("%d", par+i);
      |         ~~~~~^~~~~~~~~~~~~
magictree.cpp:166:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         scanf("%d %d %d", &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 5 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 7 ms 10452 KB Output is correct
5 Correct 7 ms 10452 KB Output is correct
6 Correct 7 ms 10452 KB Output is correct
7 Correct 7 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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 249 ms 30320 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 8 ms 10580 KB Output is correct
2 Correct 6 ms 10580 KB Output is correct
3 Correct 7 ms 10668 KB Output is correct
4 Correct 125 ms 31408 KB Output is correct
5 Correct 117 ms 31432 KB Output is correct
6 Correct 159 ms 31304 KB Output is correct

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 7 ms 10452 KB Output is correct
5 Correct 7 ms 10452 KB Output is correct
6 Correct 7 ms 10452 KB Output is correct
7 Correct 7 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 Incorrect 234 ms 32188 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 7 ms 10452 KB Output is correct
5 Correct 7 ms 10452 KB Output is correct
6 Correct 7 ms 10452 KB Output is correct
7 Correct 7 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 8 ms 10580 KB Output is correct
11 Correct 6 ms 10580 KB Output is correct
12 Correct 7 ms 10668 KB Output is correct
13 Correct 125 ms 31408 KB Output is correct
14 Correct 117 ms 31432 KB Output is correct
15 Correct 159 ms 31304 KB Output is correct
16 Incorrect 234 ms 32188 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 5 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 7 ms 10452 KB Output is correct
5 Correct 7 ms 10452 KB Output is correct
6 Correct 7 ms 10452 KB Output is correct
7 Correct 7 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 Incorrect 249 ms 30320 KB Output isn't correct
11 Halted 0 ms 0 KB -