Submission #899430

#	Time	Username	Problem	Language	Result	Execution time	Memory
899430		12345678	Magic Tree (CEOI19_magictree)	C++17	19 / 100	2065 ms	26316 KiB

magictree

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;
ll n, m, k, t[nx], w[nx], tmp[nx], x, p, sm, ans;
vector<int> d[nx];

struct value
{
    ll time;
    mutable ll val, idx;
    bool operator< (const value &o) const 
    {
        return time<o.time;
    } 
};
multiset<value> ms[nx];

void dfs(int u)
{
    for (auto v:d[u]) dfs(v);
    for (auto v:d[u]) for (auto tmp:ms[v]) ms[u].insert(tmp);
    for (auto v:d[u]) ms[v].clear();
    sm=0;
    for (auto itr=ms[u].begin(); itr!=ms[u].end(); itr++)
    {
        sm+=itr->val-tmp[itr->idx];
        tmp[itr->idx]=itr->val;
        itr->val=sm;
        itr->idx=u;
    }
    if (!t[u]) {
        for (auto vl:ms[u]) ans=max(ans, vl.val);
        return;
    }
    value nw;
    nw.time=t[u]; nw.val=w[u]; nw.idx=u;
    auto itr=ms[u].upper_bound(nw);
    if (itr!=ms[u].begin()) nw.val+=prev(itr)->val;
    itr=ms[u].insert(nw);
    while (next(itr)!=ms[u].end()&&next(itr)->val<=itr->val) ms[u].erase(next(itr));
    for (auto vl:ms[u]) ans=max(ans, vl.val);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>k;
    for (int i=2; i<=n; i++) cin>>p, d[p].push_back(i);
    for (int i=1; i<=m; i++) cin>>x>>t[x]>>w[x];
    dfs(1);
    cout<<ans<<'\n';
}

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