Submission #1093142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093142		12345678	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	294 ms	119344 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

#define ll long long

ll n, pa[nx], h[nx], c[nx];
vector<ll> d[nx];
map<ll, ll> mp[nx];

void dfs(int u)
{
    mp[u][0]=c[u];
    for (auto v:d[u])
    {
        dfs(v);
        if (mp[v].size()>mp[u].size()) swap(mp[u], mp[v]);
        for (auto [x, y]:mp[v]) mp[u][x]+=y;
    }
    mp[u][h[u]]+=0;
    mp[u][h[u]+1]+=c[u];
    auto itr=mp[u].find(h[u]);
    ll sm=-c[u], lst=h[u];
    while (1)
    {
        sm+=itr->second;
        if (sm>=0) break;
        itr=mp[u].erase(itr);
        itr--;
    }
    mp[u][itr->first]=sm;
    //cout<<"debug "<<u<<'\n';
    //cout<<"mp ";
    //for (auto x:mp[u]) cout<<x.first<<' '<<x.second<<'\n';
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>pa[i]>>h[i]>>c[i];
    for (int i=2; i<=n; i++) d[pa[i]].push_back(i);
    dfs(1);
    cout<<mp[1].begin()->second;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'void dfs(int)':
worst_reporter2.cpp:25:18: warning: unused variable 'lst' [-Wunused-variable]
   25 |     ll sm=-c[u], lst=h[u];
      |                  ^~~

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 0 / 21