Submission #418287

#	Time	Username	Problem	Language	Result	Execution time	Memory
418287		lyc	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	100 / 100	504 ms	119964 KiB

worst_reporter2

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;

const int mxN = 2e5+5;

int N, A[mxN], H[mxN], C[mxN], V;
vector<int> al[mxN], vals, cyc;
int vis[mxN], pa[mxN], onstk[mxN], incyc[mxN];
map<int,ll> dp[mxN];

void dfs(int u) {
    dp[u].insert(make_pair(0,0));
    for (int v : al[u]) {
        dfs(v);

        if (dp[v].count(H[v]+1)) dp[v][H[v]+1] += C[v];
        else dp[v].insert(make_pair(H[v]+1, C[v]));
        
        if (0 < H[v]) {
            if (dp[v].count(0)) dp[v][0] += C[v];
            else dp[v].insert(make_pair(0,C[v]));

            auto it = --dp[v].lower_bound(H[v]+1);
            while (it != dp[v].begin() && it->second <= C[v]) {
                auto x = prev(it);
                x->second += it->second;
                dp[v].erase(it);
                it = x;
            }
            it->second -= C[v];
        }

        if (SZ(dp[v]) > SZ(dp[u])) swap(dp[v],dp[u]);
        for (auto& x : dp[v]) {
            if (dp[u].count(x.first)) dp[u][x.first] += x.second;
            else dp[u].insert(x);
        }
    }
}

void dfs2(int u) {
    vis[u] = 1;
    onstk[u] = 1;
    for (int& v : al[u]) {
        if (!vis[v]) {
            pa[v] = u;
            dfs2(v);
        } else if (onstk[v]) {
            cyc.push_back(v);
            for (int x = u; x != v; x = pa[x]) cyc.push_back(x);
        }
    }
    onstk[u] = 0;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N;
    FOR(i,1,N){
        cin >> A[i] >> H[i] >> C[i];
        al[A[i]].push_back(i);
        vals.push_back(H[i]);
    }


    vals.push_back(1);
    sort(ALL(vals));
    vals.resize(unique(ALL(vals))-vals.begin());
    FOR(i,1,N){
        H[i] = lower_bound(ALL(vals),H[i])-vals.begin();
    }
    V = SZ(vals);


    ll tot = 0;
    memset(vis,0,sizeof vis);
    FOR(i,1,N) if (!vis[i]) {
        cyc.clear();
        dfs2(i);
        if (cyc.empty()) continue;

        sort(ALL(cyc), [](int u, int v){ return H[u] < H[v]; });
        for (int& u : cyc) incyc[u] = 1;

        auto& adj = al[cyc[0]];
        RFOR(j,SZ(adj)-1,0) if (incyc[adj[j]]) {
            adj.erase(adj.begin()+j);
        }
        FOR(j,1,SZ(cyc)-1){
            for (int& v : al[cyc[j]]) if (!incyc[v]) {
                adj.push_back(v);
            }
            al[cyc[j]].clear();
            al[cyc[j]].push_back(cyc[j-1]);
        }

        int root = cyc.back();
        dfs(root);
        ll ans = dp[root][0] + C[root], cur = 0;
        for (auto& x : dp[root]) {
            if (x.first > H[root]) break;
            cur += x.second;
        }
        ans = min(ans, cur);
        //TRACE(ans);
        tot += ans;
    }


    cout << tot << '\n';
}

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