Submission #467504

#	Time	Username	Problem	Language	Result	Execution time	Memory
467504		blue	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	883 ms	67972 KiB

worst_reporter2

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
using namespace std;

const int maxN = 200'000;

int N;
int A[1+maxN];
int H[1+maxN];
long long C[1+maxN];

vector<int> indegree(1+maxN, 0);
vector<int> subtree(1+maxN, 1);
vector<int> children[1+maxN];


queue<int> tbv;
map<int, long long> X[1+maxN];

void map_insert(int u, int l, long long v)
{
    if(X[u].find(l) == X[u].end()) X[u][l] = 0;
    X[u][l] += v;
}

int prv;
void merge(int u, int v) // if not cycle: u is parent, v is child
{
    if(subtree[u] < subtree[v]) swap(u, v);
    for(pair<int, long long> c: X[v])
        map_insert(u, c.first, c.second);

    X[v].clear();

    prv = u;
}


int main()
{
    cin >> N;
    for(int i = 1; i <= N; i++)
    {
        cin >> A[i] >> H[i] >> C[i];
        children[ A[i] ].push_back(i);

        indegree[ A[i] ]++;
    }

    for(int i = 1; i <= N; i++)
    {
        if(indegree[i] == 0) tbv.push(i);
    }


    while(!tbv.empty())
    {
        int u = tbv.front();
        tbv.pop();
        // cerr << "u = " << u << '\n';


        int max_child = -1;
        for(int v: children[u])
        {
            if(v == A[u] || v == u) continue;
            if(indegree[v] == 0)
            {
                if(max_child == -1 || subtree[v] > subtree[max_child])
                    max_child = v;
            }
        }

        indegree[ A[u] ]--;
        subtree[ A[u] ] += subtree[u];
        if(indegree[ A[u] ] == 0)
            tbv.push( A[u] );

        // cerr << "max child = " << max_child << '\n';

        if(max_child == -1)
        {
            map_insert(u, H[u]+1, +C[u]);
        }
        else
        {
            swap(X[u], X[max_child]);
            for(int v: children[u])
            {
                if(indegree[v] == 0 && v != max_child)
                {
                    merge(u, v);
                }
            }

            map_insert(u, 1, +C[u]);
            map_insert(u, H[u]+1, +C[u]);

            // cerr << "intermediate: ";
            // for(pair<int, long long> q: *X[u])
            // {
            //     cerr << q.first << ' ' << q.second << " | ";
            // }
            // cerr << '\n';

            long long Y = +C[u];
            while(Y > 0)
            {
                map<int, long long>::iterator it = X[u].upper_bound(H[u]);
                it--;

                // cerr << "it = " << it->first << ' ' << it->second << '\n';

                auto q = *it;
                X[u].erase(it);

                long long delta_stair = min(q.second, Y);
                q.second -= delta_stair;
                Y -= delta_stair;

                if(q.second > 0)
                    map_insert(u, q.first, q.second);
            }
        }

        // for(pair<int, long long> q: *X[u])
        // {
        //     cerr << q.first << ' ' << q.second << " | ";
        // }
        // cerr << '\n';
    }



    long long ans = 0;

    vector<bool> visit(1+N, 0);
    for(int i = 1; i <= N; i++)
    {
        if(indegree[i] == 0) continue;
        if(visit[i]) continue;

        vector<int> F{i};
        for(int u = A[i]; u != i; u = A[u])
            F.push_back(u);

        prv = i;

        for(int u:F)
        {
            visit[u] = 1;
            for(int q: children[u])
            {
                if(indegree[q] == 0)
                {
                    merge(prv, q);
                }
            }
        }

        for(int f:F)
        {
            map_insert(prv, 1, +C[f]);
            map_insert(prv, H[f], -C[f]);
            map_insert(prv, H[f]+1, +C[f]);
        }

        long long cycle_ans = 1'000'000'000'000'000'000;
        long long curr = 0;
        for(pair<int, long long> z: X[prv])
        {
            curr += z.second;
            cycle_ans = min(cycle_ans, curr);
        }

        ans += cycle_ans;
    }

    cout << ans << '\n';
}

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