Submission #899437

#	Time	Username	Problem	Language	Result	Execution time	Memory
899437		12345678	Magic Tree (CEOI19_magictree)	C++17	19 / 100	2095 ms	28864 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, sz[nx];
vector<int> d[nx];

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

void dfssz(int u)
{
    if (t[u]) sz[u]++;
    for (auto v:d[u]) dfssz(v), sz[u]+=sz[v];
}

void dfs(int u)
{
    pair<ll, int> hv={-1, -1};
    for (auto v:d[u]) dfs(v), hv=max(hv, make_pair(sz[v], v));
    if (hv.first!=-1) swap(ms[u], ms[hv.second]);
    for (auto v:d[u]) if (v!=hv.second) 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=value(t[u], w[u], 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];
    dfssz(1);
    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