oj.uz

Submission #1086606

# Submission time Handle Problem Language Result Execution time Memory
1086606 2024-09-11T06:42:17 Z Icelast Worst Reporter 4 (JOI21_worst_reporter4) C++17
100 / 100
 478 ms 208392 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
vector<int> find_cycle(vector<vector<int>> &adj){
    int n = adj.size()-1;
    vector<int> cyc(n+1, 0);
    vector<int> vis(n+1, 0), pa(n+1, -1);
    auto dfs = [&](auto dfs, int u) -> void{
        vis[u] = 1;
        for(int v : adj[u]){

            if(vis[v] == 1){
                //cycle found
                int t = u;
                while(t != v){
                    cyc[t] = v;
                    t = pa[t];
                }
                cyc[v] = v;
            }
            if(!vis[v]){
                pa[v] = u;
                dfs(dfs, v);
            }
        }
        vis[u] = 2;
    };
    for(int i = 1; i <= n; i++){
        if(vis[i]) continue;
        dfs(dfs, i);
    }
    return cyc;
}
void solve(){
    int n;
    cin >> n;
    vector<vector<int>> adj(n+1), adj_rev(n+1);
    vector<ll> h(n+1), c(n+1);
    int root = 1;
    ll sumc = 0;

    for(int i = 1; i <= n; i++){
        int v;
        cin >> v >> h[i] >> c[i];
        sumc += c[i];
        adj[i].push_back(v);
        adj_rev[v].push_back(i);
    }
    vector<int> cyc = find_cycle(adj);
    auto add = [&](map<ll, ll> &u, map<ll, ll> &v){
        if(u.size() < v.size()) swap(u, v);
        for(auto it : v){
            ll h = it.first, c = it.second;
            u[h] += c;
        }
    };
    auto fix = [&](int node, map<ll, ll> &u, ll h, ll d){
        u[h] -= d;
        u[h+1] += d;
        u[0] += d;
        if(u[h] >= 0 || cyc[node]) return;
        d = -u[h];
        u[h] = 0;
        auto it = u.lower_bound(h);
        while(it != u.begin()){
            it = prev(it);
            if(it->second <= d){
                d -= it->second;
                it = u.erase(it);
            }else{
                it->second -= d;
                break;
            }
        }
    };
    vector<map<ll, ll>> dp(n+1), res(n+1);

    auto dfs = [&](auto dfs, int u, int p) -> void{
        for(int v : adj_rev[u]){
            if(v == p || cyc[v]) continue;
            dfs(dfs, v, u);
            add(dp[u], dp[v]);
        }
        fix(u, dp[u], h[u], c[u]);
    };
    for(int i = 1; i <= n; i++){
        if(cyc[i]){
            dfs(dfs, i, i);
            add(res[cyc[i]], dp[i]);
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ll pf = 0, mn = INF;
        if(res[i].size() == 0) mn = 0;
        for(auto it : res[i]){
            pf += it.second;
            mn = min(mn, pf);
        }
        ans += mn;
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Compilation message

worst_reporter2.cpp: In function 'void solve()':
worst_reporter2.cpp:41:9: warning: unused variable 'root' [-Wunused-variable]
   41 |     int root = 1;
      |         ^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 8 ms 3480 KB Output is correct
6 Correct 6 ms 2652 KB Output is correct
7 Correct 5 ms 2260 KB Output is correct
8 Correct 8 ms 3672 KB Output is correct
9 Correct 5 ms 2652 KB Output is correct
10 Correct 4 ms 2120 KB Output is correct
11 Correct 3 ms 1884 KB Output is correct
12 Correct 5 ms 2772 KB Output is correct
13 Correct 3 ms 2648 KB Output is correct
14 Correct 6 ms 2204 KB Output is correct
15 Correct 4 ms 2140 KB Output is correct
16 Correct 11 ms 4500 KB Output is correct
17 Correct 7 ms 3088 KB Output is correct
18 Correct 3 ms 1884 KB Output is correct
19 Correct 8 ms 2816 KB Output is correct
20 Correct 4 ms 2396 KB Output is correct
21 Correct 3 ms 2396 KB Output is correct
22 Correct 5 ms 2740 KB Output is correct
23 Correct 5 ms 2140 KB Output is correct
24 Correct 6 ms 2652 KB Output is correct
25 Correct 3 ms 2396 KB Output is correct
26 Correct 5 ms 2712 KB Output is correct
27 Correct 5 ms 2652 KB Output is correct
28 Correct 5 ms 2908 KB Output is correct
29 Correct 7 ms 2972 KB Output is correct
30 Correct 8 ms 3160 KB Output is correct
31 Correct 8 ms 2952 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 8 ms 3480 KB Output is correct
6 Correct 6 ms 2652 KB Output is correct
7 Correct 5 ms 2260 KB Output is correct
8 Correct 8 ms 3672 KB Output is correct
9 Correct 5 ms 2652 KB Output is correct
10 Correct 4 ms 2120 KB Output is correct
11 Correct 3 ms 1884 KB Output is correct
12 Correct 5 ms 2772 KB Output is correct
13 Correct 3 ms 2648 KB Output is correct
14 Correct 6 ms 2204 KB Output is correct
15 Correct 4 ms 2140 KB Output is correct
16 Correct 11 ms 4500 KB Output is correct
17 Correct 7 ms 3088 KB Output is correct
18 Correct 3 ms 1884 KB Output is correct
19 Correct 8 ms 2816 KB Output is correct
20 Correct 4 ms 2396 KB Output is correct
21 Correct 3 ms 2396 KB Output is correct
22 Correct 5 ms 2740 KB Output is correct
23 Correct 5 ms 2140 KB Output is correct
24 Correct 6 ms 2652 KB Output is correct
25 Correct 3 ms 2396 KB Output is correct
26 Correct 5 ms 2712 KB Output is correct
27 Correct 5 ms 2652 KB Output is correct
28 Correct 5 ms 2908 KB Output is correct
29 Correct 7 ms 2972 KB Output is correct
30 Correct 8 ms 3160 KB Output is correct
31 Correct 8 ms 2952 KB Output is correct
32 Correct 13 ms 3420 KB Output is correct
33 Correct 466 ms 157996 KB Output is correct
34 Correct 356 ms 108188 KB Output is correct
35 Correct 431 ms 151864 KB Output is correct
36 Correct 347 ms 108184 KB Output is correct
37 Correct 183 ms 69932 KB Output is correct
38 Correct 194 ms 59184 KB Output is correct
39 Correct 186 ms 93996 KB Output is correct
40 Correct 173 ms 93980 KB Output is correct
41 Correct 107 ms 93820 KB Output is correct
42 Correct 176 ms 72280 KB Output is correct
43 Correct 199 ms 72124 KB Output is correct
44 Correct 472 ms 208392 KB Output is correct
45 Correct 330 ms 137308 KB Output is correct
46 Correct 96 ms 59436 KB Output is correct
47 Correct 293 ms 95264 KB Output is correct
48 Correct 155 ms 81392 KB Output is correct
49 Correct 133 ms 81456 KB Output is correct
50 Correct 282 ms 93856 KB Output is correct
51 Correct 108 ms 68768 KB Output is correct
52 Correct 336 ms 96168 KB Output is correct
53 Correct 151 ms 82088 KB Output is correct
54 Correct 135 ms 94080 KB Output is correct
55 Correct 267 ms 98864 KB Output is correct
56 Correct 223 ms 106220 KB Output is correct
57 Correct 201 ms 110384 KB Output is correct
58 Correct 289 ms 108844 KB Output is correct
59 Correct 288 ms 108848 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 8 ms 3480 KB Output is correct
6 Correct 6 ms 2652 KB Output is correct
7 Correct 5 ms 2260 KB Output is correct
8 Correct 8 ms 3672 KB Output is correct
9 Correct 5 ms 2652 KB Output is correct
10 Correct 4 ms 2120 KB Output is correct
11 Correct 3 ms 1884 KB Output is correct
12 Correct 5 ms 2772 KB Output is correct
13 Correct 3 ms 2648 KB Output is correct
14 Correct 6 ms 2204 KB Output is correct
15 Correct 4 ms 2140 KB Output is correct
16 Correct 11 ms 4500 KB Output is correct
17 Correct 7 ms 3088 KB Output is correct
18 Correct 3 ms 1884 KB Output is correct
19 Correct 8 ms 2816 KB Output is correct
20 Correct 4 ms 2396 KB Output is correct
21 Correct 3 ms 2396 KB Output is correct
22 Correct 5 ms 2740 KB Output is correct
23 Correct 5 ms 2140 KB Output is correct
24 Correct 6 ms 2652 KB Output is correct
25 Correct 3 ms 2396 KB Output is correct
26 Correct 5 ms 2712 KB Output is correct
27 Correct 5 ms 2652 KB Output is correct
28 Correct 5 ms 2908 KB Output is correct
29 Correct 7 ms 2972 KB Output is correct
30 Correct 8 ms 3160 KB Output is correct
31 Correct 8 ms 2952 KB Output is correct
32 Correct 13 ms 3420 KB Output is correct
33 Correct 466 ms 157996 KB Output is correct
34 Correct 356 ms 108188 KB Output is correct
35 Correct 431 ms 151864 KB Output is correct
36 Correct 347 ms 108184 KB Output is correct
37 Correct 183 ms 69932 KB Output is correct
38 Correct 194 ms 59184 KB Output is correct
39 Correct 186 ms 93996 KB Output is correct
40 Correct 173 ms 93980 KB Output is correct
41 Correct 107 ms 93820 KB Output is correct
42 Correct 176 ms 72280 KB Output is correct
43 Correct 199 ms 72124 KB Output is correct
44 Correct 472 ms 208392 KB Output is correct
45 Correct 330 ms 137308 KB Output is correct
46 Correct 96 ms 59436 KB Output is correct
47 Correct 293 ms 95264 KB Output is correct
48 Correct 155 ms 81392 KB Output is correct
49 Correct 133 ms 81456 KB Output is correct
50 Correct 282 ms 93856 KB Output is correct
51 Correct 108 ms 68768 KB Output is correct
52 Correct 336 ms 96168 KB Output is correct
53 Correct 151 ms 82088 KB Output is correct
54 Correct 135 ms 94080 KB Output is correct
55 Correct 267 ms 98864 KB Output is correct
56 Correct 223 ms 106220 KB Output is correct
57 Correct 201 ms 110384 KB Output is correct
58 Correct 289 ms 108844 KB Output is correct
59 Correct 288 ms 108848 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 1 ms 344 KB Output is correct
64 Correct 417 ms 127240 KB Output is correct
65 Correct 320 ms 93232 KB Output is correct
66 Correct 397 ms 126092 KB Output is correct
67 Correct 348 ms 92976 KB Output is correct
68 Correct 244 ms 65580 KB Output is correct
69 Correct 224 ms 57288 KB Output is correct
70 Correct 424 ms 118724 KB Output is correct
71 Correct 237 ms 92416 KB Output is correct
72 Correct 429 ms 121388 KB Output is correct
73 Correct 222 ms 96560 KB Output is correct
74 Correct 388 ms 107564 KB Output is correct
75 Correct 208 ms 82736 KB Output is correct
76 Correct 173 ms 80224 KB Output is correct
77 Correct 412 ms 119440 KB Output is correct
78 Correct 181 ms 83116 KB Output is correct
79 Correct 478 ms 149056 KB Output is correct
80 Correct 310 ms 105004 KB Output is correct
81 Correct 191 ms 83504 KB Output is correct
82 Correct 359 ms 121900 KB Output is correct
83 Correct 99 ms 87596 KB Output is correct
84 Correct 392 ms 109868 KB Output is correct
85 Correct 433 ms 120880 KB Output is correct
86 Correct 400 ms 108888 KB Output is correct
87 Correct 421 ms 118572 KB Output is correct
88 Correct 398 ms 109548 KB Output is correct