oj.uz

Submission #952130

# Submission time Handle Problem Language Result Execution time Memory
952130 2024-03-23T06:31:31 Z GrindMachine Worst Reporter 4 (JOI21_worst_reporter4) C++17
0 / 100
 545 ms 524288 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/88748?#comment-774017 (thread)
got the key idea, but didnt know how to implement in a clean way

implementation idea:
represent the subtree cost @u as a staircase function using a map
can be merged efficiently using small to large

*/

const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<ll> adj[N];
vector<pll> a(N);
vector<ll> subsiz(N);
vector<bool> on_cyc(N);

void dfs1(ll u){
    subsiz[u] = 1;
    trav(v,adj[u]){
        if(on_cyc[v]) conts;
        dfs1(v);
        subsiz[u] += subsiz[v];
    }
}

map<ll,ll> mp[N];

void dfs2(ll u){
    pll best = {-1,-1};
    trav(v,adj[u]){
        if(on_cyc[v]) conts;
        pll px = {subsiz[v],v};
        amax(best,px);
    }

    ll heavy = best.ss;
    if(heavy == -1){
        auto [h,c] = a[u];
        mp[u][1] = 0;
        mp[u][h+1] = c;
        return;
    }

    dfs2(heavy);
    mp[u] = mp[heavy];
    // swap(mp[u],mp[heavy]);

    trav(v,adj[u]){
        if(on_cyc[v]) conts;
        if(v == heavy) conts;
        dfs2(v);
        for(auto [i,x] : mp[v]){
            mp[u][i] += x;
        }
        // mp[v].clear();
    }

    auto [h,c] = a[u];
    mp[u][1] += c;
    mp[u][h] -= c;
    mp[u][h+1] += c;

    auto it = mp[u].find(h);
    vector<ll> rem;

    ll val = mp[u][h], recent_h = h; 
    while(val < 0){
        it--;
        rem.pb(recent_h);
        recent_h = it->first;
        val += it->second;
    }

    mp[u][recent_h] = val;

    trav(x,rem){
        mp[u].erase(x);
    }
}

void solve(int test_case)
{
    ll n; cin >> n;
    vector<ll> par(n+5);

    rep1(i,n){
        ll p,h,c; cin >> p >> h >> c;
        adj[p].pb(i);
        par[i] = p;
        a[i] = {h,c};
    }

    vector<ll> outdeg(n+5);
    rep1(i,n) outdeg[i] = sz(adj[i]);

    queue<ll> q;
    rep1(i,n){
        if(outdeg[i] == 0){
            q.push(i);
        }
    }

    while(!q.empty()){
        ll u = q.front();
        q.pop();

        ll p = par[u];
        outdeg[p]--;
        if(outdeg[p] == 0){
            q.push(p);
        }
    }

    rep1(i,n){
        if(outdeg[i]){
            on_cyc[i] = 1;
        }
    }

    vector<bool> vis(n+5);
    ll ans = 0;

    rep1(i,n){
        if(vis[i] or !on_cyc[i]) conts;
        ll j = i;
        map<ll,ll> sum_mp;
        vector<ll> nodes;
        ll tot_sum = 0;

        while(!vis[j]){
            vis[j] = 1;
            nodes.pb(j);
            dfs1(j);
            dfs2(j);
            sum_mp[a[j].ff] += a[j].ss;
            tot_sum += a[j].ss;
            j = par[j];
        }

        map<ll,ll> cost_mp;
        cost_mp[1] += 0;
        ll cost_sum = 0;

        trav(u,nodes){
            cost_mp[a[u].ff] += 0;
            trav(v,adj[u]){
                if(on_cyc[v]) conts;
                for(auto [i,x] : mp[v]){
                    cost_mp[i] += x;
                }
            }
        }

        ll cost = inf2;

        for(auto [h,delta] : cost_mp){
            cost_sum += delta;
            ll curr_cost = cost_sum+tot_sum-sum_mp[h];
            amin(cost,curr_cost);
        }

        ans += cost;
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19036 KB Output is correct
2 Correct 6 ms 19036 KB Output is correct
3 Correct 5 ms 19252 KB Output is correct
4 Correct 5 ms 19036 KB Output is correct
5 Correct 13 ms 22620 KB Output is correct
6 Correct 10 ms 21084 KB Output is correct
7 Correct 9 ms 20536 KB Output is correct
8 Correct 16 ms 22364 KB Output is correct
9 Correct 11 ms 21084 KB Output is correct
10 Correct 9 ms 20572 KB Output is correct
11 Correct 9 ms 20060 KB Output is correct
12 Correct 47 ms 61092 KB Output is correct
13 Correct 11 ms 23644 KB Output is correct
14 Correct 36 ms 48052 KB Output is correct
15 Correct 23 ms 34640 KB Output is correct
16 Correct 13 ms 22872 KB Output is correct
17 Correct 11 ms 21248 KB Output is correct
18 Correct 8 ms 20060 KB Output is correct
19 Correct 205 ms 245072 KB Output is correct
20 Correct 22 ms 35420 KB Output is correct
21 Correct 9 ms 21080 KB Output is correct
22 Correct 11 ms 21084 KB Output is correct
23 Correct 9 ms 20060 KB Output is correct
24 Correct 545 ms 448992 KB Output is correct
25 Correct 26 ms 36176 KB Output is correct
26 Runtime error 361 ms 524288 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19036 KB Output is correct
2 Correct 6 ms 19036 KB Output is correct
3 Correct 5 ms 19252 KB Output is correct
4 Correct 5 ms 19036 KB Output is correct
5 Correct 13 ms 22620 KB Output is correct
6 Correct 10 ms 21084 KB Output is correct
7 Correct 9 ms 20536 KB Output is correct
8 Correct 16 ms 22364 KB Output is correct
9 Correct 11 ms 21084 KB Output is correct
10 Correct 9 ms 20572 KB Output is correct
11 Correct 9 ms 20060 KB Output is correct
12 Correct 47 ms 61092 KB Output is correct
13 Correct 11 ms 23644 KB Output is correct
14 Correct 36 ms 48052 KB Output is correct
15 Correct 23 ms 34640 KB Output is correct
16 Correct 13 ms 22872 KB Output is correct
17 Correct 11 ms 21248 KB Output is correct
18 Correct 8 ms 20060 KB Output is correct
19 Correct 205 ms 245072 KB Output is correct
20 Correct 22 ms 35420 KB Output is correct
21 Correct 9 ms 21080 KB Output is correct
22 Correct 11 ms 21084 KB Output is correct
23 Correct 9 ms 20060 KB Output is correct
24 Correct 545 ms 448992 KB Output is correct
25 Correct 26 ms 36176 KB Output is correct
26 Runtime error 361 ms 524288 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19036 KB Output is correct
2 Correct 6 ms 19036 KB Output is correct
3 Correct 5 ms 19252 KB Output is correct
4 Correct 5 ms 19036 KB Output is correct
5 Correct 13 ms 22620 KB Output is correct
6 Correct 10 ms 21084 KB Output is correct
7 Correct 9 ms 20536 KB Output is correct
8 Correct 16 ms 22364 KB Output is correct
9 Correct 11 ms 21084 KB Output is correct
10 Correct 9 ms 20572 KB Output is correct
11 Correct 9 ms 20060 KB Output is correct
12 Correct 47 ms 61092 KB Output is correct
13 Correct 11 ms 23644 KB Output is correct
14 Correct 36 ms 48052 KB Output is correct
15 Correct 23 ms 34640 KB Output is correct
16 Correct 13 ms 22872 KB Output is correct
17 Correct 11 ms 21248 KB Output is correct
18 Correct 8 ms 20060 KB Output is correct
19 Correct 205 ms 245072 KB Output is correct
20 Correct 22 ms 35420 KB Output is correct
21 Correct 9 ms 21080 KB Output is correct
22 Correct 11 ms 21084 KB Output is correct
23 Correct 9 ms 20060 KB Output is correct
24 Correct 545 ms 448992 KB Output is correct
25 Correct 26 ms 36176 KB Output is correct
26 Runtime error 361 ms 524288 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -