Submission #198117

#	Time	Username	Problem	Language	Result	Execution time	Memory
198117		model_code	Magic Tree (CEOI19_magictree)	C++17	100 / 100	958 ms	53052 KiB

magictree

// 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 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17