Submission #464672

#	Time	Username	Problem	Language	Result	Execution time	Memory
464672		blue	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	741 ms	53188 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;
}


void merge(int u, int v)
{
    if(X[u] == X[v]) return;

    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();
    X[v] = X[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] ]++;
        X[i] = new map<int, long long>;
    }

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

    //First two subtasks!!!!!
    indegree[1]--;


    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
        {
            X[u] = X[max_child];
            for(int v: children[u])
            {
                if(indegree[v] == 0)
                {
                    merge(v, u);
                }
            }

            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;
    for(pair<int, long long> k: *X[1])
        if(k.first == 1)
            ans += k.second;

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

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