Submission #1080778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080778		_callmelucian	Magic Tree (CEOI19_magictree)	C++14	100 / 100	627 ms	43212 KiB

magictree

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct node {
    ll tr, lazy;
    node *lpt, *rpt;

    node() : tr(0), lazy(0), lpt(nullptr), rpt(nullptr) {}

    ll get() { return tr + lazy; }

    void pushDown () {
        if (lpt == nullptr) lpt = new node();
        if (rpt == nullptr) rpt = new node();
        lpt->lazy += lazy, rpt->lazy += lazy;
        tr += lazy, lazy = 0;
    }

    void update (int a, int b, ll incr, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) {
            lazy += incr;
            return;
        }
        pushDown();
        int mid = (l + r) >> 1;
        lpt->update(a, b, incr, l, mid);
        rpt->update(a, b, incr, mid + 1, r);
        tr = max(lpt->get(), rpt->get());
    }

    bool intr (int a, int b, int l, int r) {
        if (b < l || r < a) return 0;
        return 1;
    }

    ll query (int a, int b, int l, int r) {
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) return get();
        pushDown();
        int mid = (l + r) >> 1;
        return max(lpt->query(a, b, l, mid), rpt->query(a, b, mid + 1, r));
    }

    void destruct() {
        if (lpt != nullptr) {
            lpt->destruct();
            delete lpt; lpt = nullptr;
        }
        if (rpt != nullptr) {
            rpt->destruct();
            delete rpt; rpt = nullptr;
        }
    }
};

const int mn = 1e5 + 5;
ll dp[mn], weight[mn];
vector<int> adj[mn];
int ripe[mn], n, k;

struct item {
    node tree;
    vector<int> vec;

    item() : tree(), vec(0) {}

    void add (int id, ll val) {
        vec.push_back(id);
        ll incr = max(0LL, val - tree.query(id, id, 1, k));
        if (incr) tree.update(id, id, incr, 1, k);
    }

    void unite (item &o) {
        o.vec.push_back(k + 1);
        sort(all(o.vec)); filter(o.vec);

        vector<ll> save(o.vec.size() - 1);
        for (int i = 0; i + 1 < o.vec.size(); i++)
            save[i] = tree.query(1, o.vec[i], 1, k);

        ll best = 0;
        for (int i = 0; i + 1 < o.vec.size(); i++) {
            ll cur = o.tree.query(o.vec[i], o.vec[i], 1, k);
            best = max(best, cur);
            tree.update(o.vec[i], o.vec[i + 1] - 1, best, 1, k);
            add(o.vec[i], cur + save[i]);
        }

        o.vec.clear(); o.tree.destruct();
    }

    ll query (int l, int r) { return tree.query(l, r, 1, k); }

    void printCand() {
        sort(all(vec)); filter(vec);
        for (int u : vec)
            cout << "(" << u << ", " << tree.query(u, u, 1, k) << ") ";
        cout << "\n";
    }

    int sz() { return vec.size(); }
} node[mn];

void dfs (int u, int p) {
    for (int v : adj[u]) dfs(v, u);

    dp[u] = node[u].query(1, ripe[u]) + weight[u];
    node[u].add(ripe[u], dp[u]);

    if (node[u].sz() > node[p].sz()) swap(node[u], node[p]);
    if (u != p)
        node[p].unite(node[u]);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int m; cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) ripe[i] = 1;
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        adj[p].push_back(i);
    }

    while (m--) {
        int u; cin >> u;
        cin >> ripe[u] >> weight[u];
    }

    dfs(1, 1);
    cout << node[1].query(1, k);

    return 0;
}

Compilation message (stderr)

magictree.cpp: In member function 'void item::unite(item&)':
magictree.cpp:87:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i = 0; i + 1 < o.vec.size(); i++)
      |                         ~~~~~~^~~~~~~~~~~~~~
magictree.cpp:91:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for (int i = 0; i + 1 < o.vec.size(); i++) {
      |                         ~~~~~~^~~~~~~~~~~~~~

• 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