Submission #1093149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093149		12345678	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	311 ms	125520 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], vs[nx], ans, cy[nx];
vector<ll> d[nx], g[nx];
map<ll, ll> mp[nx];

bool dfscy(int u, int rt)
{
    //cout<<"dfscy "<<u<<'\n';
    vs[u]=1;
    bool res=0;
    for (auto v:d[u])
    {
        if (vs[v]==2) continue;
        else if (!vs[v]) res=res||dfscy(v, rt);
        else return g[rt].push_back(u), cy[u]=1, 1;
    }
    if (res) g[rt].push_back(u), cy[u]=1;
    return res;
}

void dfsfill(int u)
{
    vs[u]=2;
    for (auto v:d[u]) if (vs[u]!=2) dfsfill(v);
}

void dfs(int u)
{
    mp[u][0]=c[u];
    for (auto v:d[u])
    {
        if (cy[v]) continue;
        dfs(v);
        if (mp[v].size()>mp[u].size()) swap(mp[u], mp[v]);
        for (auto [x, y]:mp[v]) mp[u][x]+=y;
    }
    if (cy[u]) return;
    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;
}

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=1; i<=n; i++) d[pa[i]].push_back(i);
    for (int i=1; i<=n; i++) 
    {
        if (!vs[i]) 
        {
            if (dfscy(i, i))
            {
                map<ll, ll> cst;
                for (auto u:g[i])
                {
                    cst[h[u]]+=c[u];
                    dfs(u);
                    if (u==i) continue;
                    if (mp[u].size()>mp[i].size()) swap(mp[u], mp[i]);
                    for (auto [x, y]:mp[u]) mp[i][x]+=y;
                }
                //for (auto x:mp[i]) cout<<x.first<<' '<<x.second<<'\n';
                ll cur=mp[i].begin()->second, tmp=0;
                auto itr=mp[i].begin();
                for (auto [x, y]:cst)
                {
                    while (itr!=mp[i].end()&&itr->first<=x) tmp+=itr->second, itr++;
                    //cout<<"cst "<<x<<' '<<tmp<<' '<<tmp-y<<'\n';
                    cur=min(cur, tmp-y);
                }
                //cout<<"cur "<<cur<<'\n';
                ans+=cur;
            }
            dfsfill(i);
        }
    }
    /*
    cout<<"cy ";
    for (int i=1; i<=n; i++) cout<<cy[i]<<' ';
    cout<<'\n';
    */
    cout<<ans;
}

Compilation message (stderr)

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

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