oj.uz

Submission #582608

# Submission time Handle Problem Language Result Execution time Memory
582608 2022-06-24T07:27:35 Z 박상훈(#8369) Magic Tree (CEOI19_magictree) C++17
45 / 100
 577 ms 52696 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)
    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");*/
}


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 8 ms 10452 KB Output is correct
2 Correct 8 ms 10452 KB Output is correct
3 Correct 6 ms 10520 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10512 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 8 ms 10452 KB Output is correct
8 Correct 7 ms 10452 KB Output is correct
9 Correct 5 ms 10452 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 30444 KB Output is correct
2 Correct 120 ms 24616 KB Output is correct
3 Correct 577 ms 52696 KB Output is correct
4 Correct 334 ms 35568 KB Output is correct
5 Correct 416 ms 35660 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10580 KB Output is correct
2 Correct 6 ms 10660 KB Output is correct
3 Correct 6 ms 10580 KB Output is correct
4 Correct 126 ms 31408 KB Output is correct
5 Correct 117 ms 31404 KB Output is correct
6 Correct 200 ms 31304 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 28160 KB Output is correct
2 Correct 152 ms 27204 KB Output is correct
3 Correct 95 ms 24000 KB Output is correct
4 Correct 106 ms 31700 KB Output is correct
5 Correct 73 ms 27340 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10452 KB Output is correct
2 Correct 8 ms 10452 KB Output is correct
3 Correct 6 ms 10520 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10512 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 8 ms 10452 KB Output is correct
8 Correct 7 ms 10452 KB Output is correct
9 Correct 5 ms 10452 KB Output is correct
10 Incorrect 223 ms 32216 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 20 ms 12628 KB Output is correct
2 Correct 115 ms 20568 KB Output is correct
3 Correct 83 ms 20576 KB Output is correct
4 Correct 86 ms 20564 KB Output is correct
5 Correct 75 ms 25412 KB Output is correct
6 Correct 86 ms 23628 KB Output is correct
7 Correct 60 ms 21944 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10452 KB Output is correct
2 Correct 8 ms 10452 KB Output is correct
3 Correct 6 ms 10520 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10512 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 8 ms 10452 KB Output is correct
8 Correct 7 ms 10452 KB Output is correct
9 Correct 5 ms 10452 KB Output is correct
10 Correct 6 ms 10580 KB Output is correct
11 Correct 6 ms 10660 KB Output is correct
12 Correct 6 ms 10580 KB Output is correct
13 Correct 126 ms 31408 KB Output is correct
14 Correct 117 ms 31404 KB Output is correct
15 Correct 200 ms 31304 KB Output is correct
16 Incorrect 223 ms 32216 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10452 KB Output is correct
2 Correct 8 ms 10452 KB Output is correct
3 Correct 6 ms 10520 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10512 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 8 ms 10452 KB Output is correct
8 Correct 7 ms 10452 KB Output is correct
9 Correct 5 ms 10452 KB Output is correct
10 Correct 243 ms 30444 KB Output is correct
11 Correct 120 ms 24616 KB Output is correct
12 Correct 577 ms 52696 KB Output is correct
13 Correct 334 ms 35568 KB Output is correct
14 Correct 416 ms 35660 KB Output is correct
15 Correct 6 ms 10580 KB Output is correct
16 Correct 6 ms 10660 KB Output is correct
17 Correct 6 ms 10580 KB Output is correct
18 Correct 126 ms 31408 KB Output is correct
19 Correct 117 ms 31404 KB Output is correct
20 Correct 200 ms 31304 KB Output is correct
21 Correct 145 ms 28160 KB Output is correct
22 Correct 152 ms 27204 KB Output is correct
23 Correct 95 ms 24000 KB Output is correct
24 Correct 106 ms 31700 KB Output is correct
25 Correct 73 ms 27340 KB Output is correct
26 Incorrect 223 ms 32216 KB Output isn't correct
27 Halted 0 ms 0 KB -