oj.uz

Submission #899425

# Submission time Handle Problem Language Result Execution time Memory
899425 2024-01-06T07:15:40 Z 12345678 Magic Tree (CEOI19_magictree) C++17
0 / 100
 133 ms 22720 KB 
#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();
    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]) {
        //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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 15444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 22720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8792 KB Output isn't correct
2 Halted 0 ms 0 KB -