oj.uz

Submission #198117

# Submission time Handle Problem Language Result Execution time Memory
198117 2020-01-24T18:19:10 Z model_code Magic Tree (CEOI19_magictree) C++17
100 / 100
 958 ms 53052 KB 
// Compressed Fenwick trees over implicit HLD. Compression done using map<>.
// O(N log^2 N)
#include <bits/stdc++.h>
using namespace std;

using wgt = unsigned long long;

class Solver {
    using day = int;

    class IntervalTree {
        struct node {
            wgt val, add;
            int l, r;
        };        

        vector<node> T;

        void upd(int i) {
            node & n = T[i];
            n.val += n.add;
            if(n.l+1 < n.r) {
                T[2*i].add += n.add;
                T[2*i+1].add += n.add;
            }
            n.add = 0;
        }

    public:
        IntervalTree() {}

        IntervalTree(int N) {
            int b = 1;
            while(b < N) b *= 2;
            T.reserve(2*b+1);
            T.resize(2, {0, 0, 0, b});
            for(int i = 1; ; i++) {
                if(i == (int)T.size() || T[i].l+1 == T[i].r) break;
                T.push_back({0, 0, T[i].l, (T[i].l+T[i].r)/2});
                T.push_back({0, 0, (T[i].l+T[i].r)/2, T[i].r});
            }
        }

        void add(int l, int r, wgt w_add, int i = 1) {
            node & n = T[i];
            if(n.l == l && n.r == r) {
                n.add += w_add;
                upd(i);
                return;
            }
            else if(n.add) upd(i);
            if(n.l >= r || l >= n.r) return;
            int c = (n.l + n.r) / 2;
            if(n.l+1 < n.r) {
                add(l, min(r, c), w_add, 2*i);
                add(max(l, c), r, w_add, 2*i+1);
                n.val = max(T[2*i].val, T[2*i+1].val);
            }
        }

        void put(int pos, wgt w, int i = 1) {
            node & n = T[i];
            if(n.l == pos && n.r == pos+1) {
                T[i].val = w;
                T[i].add = 0;
                return;
            }
            else if(n.add) upd(i);
            if(n.l > pos || pos >= n.r) return;
            put(pos, w, 2*i);
            put(pos, w, 2*i+1);
            n.val = max(T[2*i].val, T[2*i+1].val);
        }

        wgt get_max(int pos, int i = 1) { // max [l..r)
            node & n = T[i];
            if(n.add) upd(i);
            if(pos < n.l) return 0;
            if(n.r == pos+1) return n.val;
            int c = (n.l + n.r) / 2;
            wgt best_lft = get_max(min(pos, c-1), 2*i);
            if(pos < c) return best_lft;
            wgt best_rt  = get_max(pos, 2*i+1);
            return max(best_lft, best_rt);
        }
    };

    int N;
    vector< vector<int> > son;
    vector<wgt> W;
    vector<day> D;
    vector<int> sz, max_son;
    vector<wgt> LIS_W; // largest increasing subgraph weight

    void DFS_init(int R) {
        int max_son_sz = 0;
        for(auto v : son[R]) {
            DFS_init(v);
            sz[R] += sz[v];
            if(sz[v] > max_son_sz) {
                max_son_sz = sz[v];
                max_son[R] = v;
            }
        }
    }

    void compress(int R, map<day, int> & this_map, bool top = true) {
        if(D[R]) this_map[D[R]-1] = 0;
        for(auto v : son[R]) compress(v, this_map, false);
        if(top) {
            int n = 0;
            for(auto & p : this_map) p.second = n++;
        }
    }

    void DFS_solve(int R, map<day, int> & this_map, IntervalTree & this_ftree) {
        if(max_son[R] == 0) {
            if(D[R] > 0) {
                LIS_W[R] = W[R];
                this_ftree.put(this_map[D[R]-1], W[R]);
            }
            return;
        }

        DFS_solve(max_son[R], this_map, this_ftree);

        for(auto v : son[R]) if(v != max_son[R]) {
            map<int, int> subtree_D_map;
            compress(v, subtree_D_map);
            int m = subtree_D_map.size();

            IntervalTree subtree_ftree(m);

            DFS_solve(v, subtree_D_map, subtree_ftree);

            for(auto it = rbegin(subtree_D_map); it != rend(subtree_D_map); it++) {
                // keys in this_map are a superset of keys for subtree_D_map
                int this_compr_id = this_map[it->first];
                int subtree_compr_id = it->second;
                int this_compr_id_nxt;
                if(it == rbegin(subtree_D_map)) this_compr_id_nxt = this_map.size();
                else {
                    auto jt = it;
                    jt--;
                    this_compr_id_nxt = this_map[jt->first];
                }
                wgt orig_value = this_ftree.get_max(this_compr_id);
                wgt subtree_incr = subtree_ftree.get_max(subtree_compr_id);
                this_ftree.put(this_compr_id, orig_value);
                this_ftree.add(this_compr_id, this_compr_id_nxt, subtree_incr);
            }
        }

        if(D[R] > 0) {
            int this_compr_id = this_map[D[R]-1];
            LIS_W[R] = this_ftree.get_max(this_compr_id) + W[R];
            this_ftree.put(this_compr_id, LIS_W[R]);
        }
    }

public:
    Solver(vector< vector<int> > & son_, vector<wgt> & W_, vector<day> & D_) : N(son_.size()), son(son_), W(W_), D(D_) {
        // D[v] == 0: v is empty
        sz.resize(N, 1);
        max_son.resize(N, 0); // 0: leaf
        LIS_W.resize(N, 0);

        DFS_init(0);
    }

    wgt solve() {
        map<day, int> full_D_map;
        compress(0, full_D_map);
        int m = full_D_map.size();
        IntervalTree full_ftree(m);

        DFS_solve(0, full_D_map, full_ftree);

        return full_ftree.get_max(m-1);
    }
};

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> par(N, 0);
    vector< vector<int> > son(N);
    for(int i = 1; i < N; i++) {
        cin >> par[i];
        par[i]--;
        son[par[i]].push_back(i);
    }
    vector<wgt> W(N, 0);
    vector<int> D(N, 0);
    for(int i = 0; i < M; i++) {
        int v, d, w;
        cin >> v >> d >> w;
        v--;
        D[v] = d;
        W[v] = w;
    }
    Solver solver(son, W, D);
    cout << solver.solve() << "\n";
}

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 16416 KB Output is correct
2 Correct 203 ms 30456 KB Output is correct
3 Correct 958 ms 20252 KB Output is correct
4 Correct 493 ms 16244 KB Output is correct
5 Correct 544 ms 19576 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 306 ms 52988 KB Output is correct
5 Correct 303 ms 52904 KB Output is correct
6 Correct 418 ms 53052 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 12572 KB Output is correct
2 Correct 280 ms 12568 KB Output is correct
3 Correct 257 ms 26800 KB Output is correct
4 Correct 195 ms 10352 KB Output is correct
5 Correct 244 ms 46884 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 339 ms 12692 KB Output is correct
11 Correct 291 ms 12564 KB Output is correct
12 Correct 232 ms 26872 KB Output is correct
13 Correct 171 ms 10292 KB Output is correct
14 Correct 219 ms 46840 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2936 KB Output is correct
2 Correct 122 ms 12700 KB Output is correct
3 Correct 119 ms 12664 KB Output is correct
4 Correct 115 ms 12664 KB Output is correct
5 Correct 47 ms 10224 KB Output is correct
6 Correct 105 ms 18424 KB Output is correct
7 Correct 109 ms 27000 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 4 ms 760 KB Output is correct
11 Correct 2 ms 888 KB Output is correct
12 Correct 4 ms 760 KB Output is correct
13 Correct 306 ms 52988 KB Output is correct
14 Correct 303 ms 52904 KB Output is correct
15 Correct 418 ms 53052 KB Output is correct
16 Correct 339 ms 12692 KB Output is correct
17 Correct 291 ms 12564 KB Output is correct
18 Correct 232 ms 26872 KB Output is correct
19 Correct 171 ms 10292 KB Output is correct
20 Correct 219 ms 46840 KB Output is correct
21 Correct 105 ms 3496 KB Output is correct
22 Correct 407 ms 13184 KB Output is correct
23 Correct 494 ms 19164 KB Output is correct
24 Correct 847 ms 21500 KB Output is correct
25 Correct 393 ms 15952 KB Output is correct
26 Correct 526 ms 28908 KB Output is correct
27 Correct 496 ms 37524 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 310 ms 16416 KB Output is correct
11 Correct 203 ms 30456 KB Output is correct
12 Correct 958 ms 20252 KB Output is correct
13 Correct 493 ms 16244 KB Output is correct
14 Correct 544 ms 19576 KB Output is correct
15 Correct 4 ms 760 KB Output is correct
16 Correct 2 ms 888 KB Output is correct
17 Correct 4 ms 760 KB Output is correct
18 Correct 306 ms 52988 KB Output is correct
19 Correct 303 ms 52904 KB Output is correct
20 Correct 418 ms 53052 KB Output is correct
21 Correct 297 ms 12572 KB Output is correct
22 Correct 280 ms 12568 KB Output is correct
23 Correct 257 ms 26800 KB Output is correct
24 Correct 195 ms 10352 KB Output is correct
25 Correct 244 ms 46884 KB Output is correct
26 Correct 339 ms 12692 KB Output is correct
27 Correct 291 ms 12564 KB Output is correct
28 Correct 232 ms 26872 KB Output is correct
29 Correct 171 ms 10292 KB Output is correct
30 Correct 219 ms 46840 KB Output is correct
31 Correct 30 ms 2936 KB Output is correct
32 Correct 122 ms 12700 KB Output is correct
33 Correct 119 ms 12664 KB Output is correct
34 Correct 115 ms 12664 KB Output is correct
35 Correct 47 ms 10224 KB Output is correct
36 Correct 105 ms 18424 KB Output is correct
37 Correct 109 ms 27000 KB Output is correct
38 Correct 105 ms 3496 KB Output is correct
39 Correct 407 ms 13184 KB Output is correct
40 Correct 494 ms 19164 KB Output is correct
41 Correct 847 ms 21500 KB Output is correct
42 Correct 393 ms 15952 KB Output is correct
43 Correct 526 ms 28908 KB Output is correct
44 Correct 496 ms 37524 KB Output is correct
45 Correct 113 ms 3316 KB Output is correct
46 Correct 392 ms 13256 KB Output is correct
47 Correct 512 ms 19168 KB Output is correct
48 Correct 891 ms 22072 KB Output is correct
49 Correct 444 ms 15948 KB Output is correct
50 Correct 587 ms 28896 KB Output is correct
51 Correct 549 ms 37572 KB Output is correct