Submission #1094434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094434		vladilius	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	413 ms	162968 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> a(n + 1), h(n + 1), c(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i]>>h[i]>>c[i];
    }
    
    vector<pii> all;
    for (int i = 1; i <= n; i++) all.pb({h[i], i});
    sort(all.begin(), all.end());
    int i = 0, cc = 0;
    while (i < all.size()){
        int j = i;
        while (j < all.size() && all[i] == all[j]){
            j++;
        }
        cc++;
        while (i < j){
            h[all[i].ss] = cc;
            i++;
        }
    }
    
    vector<int> g1[n + 1];
    for (int i = 1; i <= n; i++){
        if (a[i] != i) g1[a[i]].pb(i);
    }
    vector<bool> used(n + 1), seen(n + 1);
    vector<int> dd(n + 1), d[n + 1], pp(n + 1);
    function<void(int)> dfs = [&](int v){
        seen[v] = used[v] = 1;
        for (int i: g1[v]){
            if (used[i]){
                if (seen[i]){
                    dd[i] = v;
                    for (int j = v; j != i; j = pp[j]){
                        dd[j] = v;
                    }
                }
                continue;
            }
            pp[i] = v;
            dfs(i);
        }
        seen[v] = 0;
    };
    
    for (int i = 1; i <= n; i++){
        if (!used[i]){
            dfs(i);
        }
    }
    
    vector<int> g[n + 1];
    for (int i = 1; i <= n; i++){
        if (!dd[i]) dd[i] = i;
        d[dd[i]].pb(i);
    }
    fill(used.begin(), used.end(), 0);
    for (int i = 1; i <= n; i++){
        int x = dd[a[i]], y = dd[i];
        if (x != y){
            g[x].pb(y);
            used[y] = 1;
        }
    }
    
    vector<ll> sum(cc + 1);
    map<int, ll> mp[n + 1];
    
    auto add = [&](int v, int l, int r, ll x){
        mp[v][l] += x;
        if (r < cc) mp[v][r + 1] -= x;
    };
    
    function<void(int)> solve = [&](int v){
        for (int i: g[v]) solve(i);
        
        for (int i: g[v]){
            if (mp[v].size() < mp[i].size()) swap(mp[v], mp[i]);
            for (auto [p, x]: mp[i]){
                mp[v][p] += x;
            }
        }
        
        ll S = 0;
        for (int i: d[v]) S += c[i];
        
        map<int, ll> t;
        for (int i: d[v]){
            t[h[i]] += c[i];
        }
    
        add(v, 1, cc, S);
        
        for (auto [i, S]: t){
            auto it = mp[v].upper_bound(i);
            if (it == mp[v].begin()) continue;
            it--;
            if (i < cc) mp[v][i + 1] += S;
            ll x = S; int r = -1;
            while ((*it).ss < x) {
                r = (*it).ff;
                x -= (*it).ss;
                if (it == mp[v].begin()) break;
                it--;
            }
            it -> ss -= x;
            if (r != -1){
                while (true){
                    it = mp[v].lower_bound(r);
                    if (it == mp[v].end() || (*it).ff > i) break;
                    mp[v].erase(it);
                }
            }
        }
    };
    ll out = 0;
    for (int i = 1; i <= n; i++){
        if (!used[i]){
            solve(i);
            out += (*mp[i].begin()).ss;
        }
    }
    cout<<out<<"\n";
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:25:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     while (i < all.size()){
      |            ~~^~~~~~~~~~~~
worst_reporter2.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         while (j < all.size() && all[i] == all[j]){
      |                ~~^~~~~~~~~~~~

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