Submission #723777

#	Time	Username	Problem	Language	Result	Execution time	Memory
723777		drdilyor	Worm Worries (BOI18_worm)	C++17	0 / 100	15 ms	27632 KiB

worm

#include<bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
struct node {
    ll mx = 0;
    int size = 1;
    node* l = nullptr;
    node* r = nullptr;
    node* getl() {
        if (l==nullptr) l = new node{};
        return l;
    }
    node* getr() {
        if (r == nullptr) r = new node{};
        return r;
    }

    void update(int l, int r, ll x, int tl, int tr) {
        if (l <= tl && tr <= r) {
            mx = max(mx, x);
            return;
        }
        if (r < tl || tr < l) return;
        int mid = (tl+tr) /2;
        getl()->update(l, r, x, tl, mid);
        getr()->update(l, r, x, mid+1, tr);
        size = getl()->size + getr()->size;
    }

    ll query(int i, int tl, int tr) {
        if (tl == tr) return mx;
        int mid = (tl+tr) / 2;
        ll res = i <= mid ? getl()->query(i, tl, mid) : getr()->query(i, mid+1, tr);
        size = (l ? l->size : 0) + (r ? r->size : 0);
        return max(mx, res);
    }
};

void merge(node*& a, node*& b) {
    if (!b) return;
    if (!a) a = b;
    else {
        if (a->size < b->size)
            swap(a, b);
        a->mx += b->mx;
        if (b->l) merge(a->l, b->l);
        if (b->r) merge(a->r, b->r);
        a->size = (a->l ? a->l->size : 0) + (a->r ? a->r->size : 0);
    }
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
 
    vector<vector<int>> child(n);
    vector par(n, -1);
    for (int i = 1; i < n; i++) {
        cin >> par[i];
        child[--par[i]].push_back(i);
    }
 
    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];
 
    function<void(node*)> print = [&](node* st) {
        cout << st->mx << '{';
        if (st->l) print(st->l);
        cout << ',';
        if (st->r) print(st->r);
        cout << "} ";
    };

    auto dp = [&](auto& dp, int i)->set<pair<int,int>> {
        set<pair<int,int>> res;
        int d = fruit[i].first;
#define debug cout << "res=[";for(auto[a,b] : res) cout << a<<':'<<b <<' ';cout << "] ec=[";for (auto [a,b]: ec) cout << a <<':'<<b<<' ';cout << "]\n";
        for (int e : child[i]) {
            auto ec = dp(dp, e);
            if (ec.size() > res.size())
                swap(ec, res);
            for (auto [j, x] : ec) {
                int y = 0;
                auto it = res.lower_bound({j+1, -1});
                if (it!=res.begin()) {
                    it--;
                    y =it->second;
                }
                it = res.lower_bound({j, -1});
                if (it->second == j) {
                    res.erase(it);
                }
                res.insert({j, x + y});
            }
            debug;
        }

        auto ec = res;
        if (d) {
            auto it = res.lower_bound({d, -1});
            int x = 0;
            if (it != res.end()) {
                it--;
                x = it->second;
            }

            x += fruit[i].second;
            auto jt = res.lower_bound({d, -1});
            if (jt != res.end()) {
                if (jt->first == d && jt->second < x) {
                    res.erase(jt);
                    res.insert({d, x});
                }
            } else {
                res.insert({d, x});
            }
            cout << d << ' ' << x << '\n';
            while (true) {
            debug;
                auto it = res.lower_bound({d+1, -1});
                if (it == res.end() || it->second > x) break;
                res.erase(it);
            }
        }
        cout << i << ' '; for (auto [a, b] : res) cout << a<<':'<<b << ' '; cout << endl;
        return res;
    };
    //cout << dp(dp, 0).rbegin()->second << '\n';

    if (n <= 10000) {
        auto dp2 = [&](auto& dp, int i)->vector<ll>{
            vector<vector<ll>> dpc;
            for (int e : child[i])
                dpc.push_back(dp(dp, e));
     
            vector<ll> res(k+1);
            for (int day = 1; day <= k; day++) {
                for (int j = 0; j < (int)dpc.size(); j++)
                    res[day] += dpc[j][day];
            }
            int d = fruit[i].first;
            if (d) {
                res[d] = max(res[d], res[d-1] + fruit[i].second);
                for (int i = d+1; i <= k; i++)
                    res[i] = max(res[i], res[d]);
            }
            return res;
        };
        cout << dp2(dp2, 0)[k] << '\n';
    }
    else {
    }
}

Compilation message (stderr)

worm.cpp: In function 'int main()':
worm.cpp:88:10: warning: variable 'dp' set but not used [-Wunused-but-set-variable]
   88 |     auto dp = [&](auto& dp, int i)->set<pair<int,int>> {
      |          ^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 22
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 14
• Subtask 6: 0 / 23