Submission #723791

#	Time	Username	Problem	Language	Result	Execution time	Memory
723791		drdilyor	Magic Tree (CEOI19_magictree)	C++17	48 / 100	218 ms	25344 KiB

magictree

#include<bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
struct segtree {
    int n;
    vector<ll> t;
    segtree(int m) : n(m), t(m*4) {}
    void update(int l, int r, ll x, int v, int tl, int tr) {
        if (l <= tl && tr <= r) {
            t[v] = max(t[v], x);
        } else if (tr < l || r < tl) {
            return;
        } else {
            int mid = (tl+tr) / 2;
            update(l, r, x, v*2, tl, mid);
            update(l, r, x, v*2+1, mid+1, tr);
        }
    }
    ll query(int i, int v, int tl, int tr) {
        if (tl == tr) return t[v];
        int mid = (tl+tr) / 2;
        if (i <= mid) return max(t[v], query(i, v*2, tl, mid));
        else return max(t[v], query(i, v*2+1, mid+1, tr));
    }
};
 
int main() {
    int n, m, k;
    cin >> n >> m >> k;
 
    vector<vector<int>> child(n);
    vector par(n, -1);
    bool line = 1;
    for (int i = 1; i < n; i++) {
        cin >> par[i];
        child[--par[i]].push_back(i);
        line &= par[i] == i-1;
    }
 
    map<int,int> comp;
    vector<pair<int,int>> fruit(n);
    for (int i =0; i < m;i ++) {
        ll v, d, w;
        cin >> v >> d >> w;
        v--;
        comp[d] = 0;
        fruit[v] = {d, w};
    }
 
    k = 0;
    for (auto& mp: comp) mp.second = ++k;
    for (auto& [d, w] : fruit)
        d = comp[d];
 
    if (k <= 20) {
        auto dp = [&](auto& dp, int i)->vector<ll>*{

            vector<vector<ll>*> dpc;
            for (int e : child[i])
                dpc.push_back(dp(dp, e));
     
            vector<ll>& res = *(dpc.empty() ? new vector<ll>(k+1) : dpc[0]);
            for (int day = 1; day <= k; day++) {
                for (int j = 1; j < (int)dpc.size(); j++)
                    res[day] += (*dpc[j])[day];
                if (day == fruit[i].first)
                    res[day] += fruit[i].second;
            }
            int d = fruit[i].first;
            if (d) {
                res[d] = max(res[d], res[d-1]);
                for (int i = d+1; i <= k; i++)
                    res[i] = max(res[i], res[d]);
            }
            return &res;
        };
        cout << (*dp(dp, 0))[k] << '\n';
    } else if (line) {
        auto dp = [&](auto& dp, int i)->segtree* {
     
            segtree* res(nullptr);
            for (int e : child[i]) {
                res = dp(dp, e);
            }
            if (!res) res = new segtree(k+1);
            int d = fruit[i].first;
            res->update(d, d, res->query(d, 1, 0, k) + fruit[i].second,1, 0, k);
            if (d) {
                res->update(d, d, res->query(d-1, 1, 0, k),1, 0, k);
                res->update(d+1, k, res->query(d, 1, 0, k),1, 0, k);
            }
            return res;
        };
        cout << dp(dp, 0)->query(k, 1, 0, k) << '\n';
    } else {
        ll res = 0;
        for (auto [a, b] : fruit) res += b;
        cout << res << '\n';
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17