oj.uz

Submission #582626

# Submission time Handle Problem Language Result Execution time Memory
582626 2022-06-24T07:44:35 Z 박상훈(#8369) Magic Tree (CEOI19_magictree) C++17
45 / 100
 489 ms 56420 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);

        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(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:160:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |     scanf("%lld %lld %lld", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:164:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |         scanf("%lld", par+i);
      |         ~~~~~^~~~~~~~~~~~~~~
magictree.cpp:170:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |         scanf("%lld %lld %lld", &v, &d, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10512 KB Output is correct
2 Correct 6 ms 10392 KB Output is correct
3 Correct 7 ms 10504 KB Output is correct
4 Correct 6 ms 10392 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 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 252 ms 32576 KB Output is correct
2 Correct 106 ms 27620 KB Output is correct
3 Correct 489 ms 56420 KB Output is correct
4 Correct 326 ms 39080 KB Output is correct
5 Correct 354 ms 39360 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10708 KB Output is correct
2 Correct 9 ms 10744 KB Output is correct
3 Correct 7 ms 10708 KB Output is correct
4 Correct 119 ms 34824 KB Output is correct
5 Correct 110 ms 34924 KB Output is correct
6 Correct 175 ms 34804 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 30384 KB Output is correct
2 Correct 144 ms 29544 KB Output is correct
3 Correct 116 ms 26648 KB Output is correct
4 Correct 119 ms 34036 KB Output is correct
5 Correct 72 ms 30920 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10512 KB Output is correct
2 Correct 6 ms 10392 KB Output is correct
3 Correct 7 ms 10504 KB Output is correct
4 Correct 6 ms 10392 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 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 Incorrect 228 ms 34460 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 22 ms 13176 KB Output is correct
2 Correct 111 ms 22756 KB Output is correct
3 Correct 97 ms 22668 KB Output is correct
4 Correct 91 ms 22824 KB Output is correct
5 Correct 72 ms 27880 KB Output is correct
6 Correct 90 ms 26760 KB Output is correct
7 Correct 80 ms 25032 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10512 KB Output is correct
2 Correct 6 ms 10392 KB Output is correct
3 Correct 7 ms 10504 KB Output is correct
4 Correct 6 ms 10392 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 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 6 ms 10708 KB Output is correct
11 Correct 9 ms 10744 KB Output is correct
12 Correct 7 ms 10708 KB Output is correct
13 Correct 119 ms 34824 KB Output is correct
14 Correct 110 ms 34924 KB Output is correct
15 Correct 175 ms 34804 KB Output is correct
16 Incorrect 228 ms 34460 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 10512 KB Output is correct
2 Correct 6 ms 10392 KB Output is correct
3 Correct 7 ms 10504 KB Output is correct
4 Correct 6 ms 10392 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 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 252 ms 32576 KB Output is correct
11 Correct 106 ms 27620 KB Output is correct
12 Correct 489 ms 56420 KB Output is correct
13 Correct 326 ms 39080 KB Output is correct
14 Correct 354 ms 39360 KB Output is correct
15 Correct 6 ms 10708 KB Output is correct
16 Correct 9 ms 10744 KB Output is correct
17 Correct 7 ms 10708 KB Output is correct
18 Correct 119 ms 34824 KB Output is correct
19 Correct 110 ms 34924 KB Output is correct
20 Correct 175 ms 34804 KB Output is correct
21 Correct 167 ms 30384 KB Output is correct
22 Correct 144 ms 29544 KB Output is correct
23 Correct 116 ms 26648 KB Output is correct
24 Correct 119 ms 34036 KB Output is correct
25 Correct 72 ms 30920 KB Output is correct
26 Incorrect 228 ms 34460 KB Output isn't correct
27 Halted 0 ms 0 KB -