제출 #1362380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1362380		alexdd	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	100 / 100	343 ms	170828 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 2e5 + 5;
const int MAXV = 1e9 + 2;

int n;
int parent[MAXN], h[MAXN], c[MAXN];
vector<int> con[MAXN];

bool oncyc[MAXN], done[MAXN];

map<int,int> difdp[MAXN];
void dfs(int nod)
{
    assert(!done[nod]);
    done[nod] = 1;

    int maxc = -1, heavy = -1;
    for(int adj:con[nod])
    {
        if(oncyc[adj])
            continue;

        dfs(adj);
        if((int)difdp[adj].size() > maxc)
            maxc = (int)difdp[adj].size(), heavy = adj;
    }

    if(heavy == -1)
    {
        if(oncyc[nod])
            return;

        difdp[nod][h[nod]] = 0;
        difdp[nod][h[nod] + 1] = c[nod];
        difdp[nod][MAXV] = 0;
    }
    else
    {
        swap(difdp[nod], difdp[heavy]);
        for(int adj:con[nod])
        {
            if(oncyc[adj] || adj == heavy)
                continue;
            for(auto it:difdp[adj])
            {
                difdp[nod][it.first] += it.second;
            }
        }

        if(oncyc[nod])
            return;

        difdp[nod][1] += c[nod];

        int ramas = c[nod];
        auto it = difdp[nod].upper_bound(h[nod]);
        assert(it != difdp[nod].begin());
        it--;
        assert(it != difdp[nod].end());
        while(ramas > 0)
        {
            int mnm = min(ramas, (*it).second);
            (*it).second -= mnm;
            ramas -= mnm;
            if(ramas == 0)
                break;

            (*it).second = 0;
            it = difdp[nod].erase(it);
            assert(it != difdp[nod].begin());
            it--;
        }

        difdp[nod][h[nod] + 1] += c[nod];
    }
}

int visited[MAXN], pas;

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>parent[i]>>h[i]>>c[i];
        con[parent[i]].push_back(i);
    }

    int rez = 0;

    for(int i=1;i<=n;i++)
    {
        if(done[i])
            continue;

        int cur = i;
        pas++;
        while(visited[cur] != pas)
        {
            visited[cur] = pas;
            cur = parent[cur];
        }

        int capat = cur;
        vector<int> cyc;
        while(1)
        {
            cyc.push_back(cur);
            cur = parent[cur];
            if(cur == capat)
                break;
        }

        for(int x:cyc)
            oncyc[x] = 1;

        for(int x:cyc)
            dfs(x);

        int totc = 0;
        map<int,int> tot, sumc;
        for(int x:cyc)
        {
            totc += c[x];
            sumc[h[x]] -= c[x];
            tot[h[x]] += 0;
            for(auto it:difdp[x])
                tot[it.first] += it.second;
        }

        int pref = 0;
        int aux = 1e18;
        for(auto it:tot)
        {
            pref += it.second;
            aux = min(aux, pref + (totc + sumc[it.first]));
        }

        rez += aux;
    }

    cout<<rez;

    return 0;
}

• 서브태스크 1: 14 / 14
• 서브태스크 2: 65 / 65
• 서브태스크 3: 21 / 21