Submission #899428

#	Time	Username	Problem	Language	Result	Execution time	Memory
899428		12345678	Magic Tree (CEOI19_magictree)	C++17	19 / 100	2043 ms	28188 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;
        //cout<<"here"<<' '<<vl.time<<' '<<vl.val<<' '<<vl.idx<<'\n';
    }
    if (!t[u]) {
        for (auto vl:ms[u]) ans=max(ans, vl.val);
        //cout<<"current: "<<u<<'\n';
        //for (auto vl:ms[u]) cout<<vl.time<<' '<<vl.val<<' '<<vl.idx<<'\n';
        return;
    }
    //cout<<"current1: "<<u<<'\n';
    //for (auto vl:ms[u]) cout<<vl.time<<' '<<vl.val<<' '<<vl.idx<<'\n';
    value nw;
    nw.time=t[u]; nw.val=LLONG_MAX; nw.idx=LLONG_MAX;
    auto itr=ms[u].upper_bound(nw);
    if (itr==ms[u].begin()) nw.val=w[u], nw.idx=u;
    else nw.val=w[u]+prev(itr)->val, nw.idx=u;
    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);
    //cout<<"current2: "<<u<<'\n';
    //for (auto vl:ms[u]) cout<<vl.time<<' '<<vl.val<<' '<<vl.idx<<'\n';
}

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