oj.uz

Submission #733086

# Submission time Handle Problem Language Result Execution time Memory
733086 2023-04-30T04:50:14 Z baokhue232005 Worst Reporter 4 (JOI21_worst_reporter4) C++14
79 / 100
 327 ms 69616 KB 
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option

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

#define all(flg) flg.begin(), flg.end()
#define int long long
#define pb push_back
#define fi first
#define se second
#define eb emplace_back
#define ii pair<int, int>
#define vi vector<int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define ld long double
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 2e5 +  5;
const ll oo = 1e18 + 7;
int n, a[maxN];
int x, y, z, k;

int bonus = 0;
int val[maxN], cost[maxN];
int chi[maxN];

bool trigg[maxN];
int sum = 0;
vi vc[maxN];

int par[maxN];
int find(int i){
    if(i == par[i]) return i;
    return par[i] = find(par[i]);
}

void dfs(int node, map<int, int>& mp){
    mp[0] = oo;
    for(int cc : vc[node]){
        map<int, int> sec;
        dfs(cc, sec);
        if(mp.size() < sec.size()) swap(mp, sec);
        for(ii pr : sec) mp[pr.fi] += pr.se;
    }
    if(node == 0){
        mp[0] = 0;
        int ans = 0;
        for(ii pr : mp) ans += pr.se;
        cout << sum - ans << endl;
        exit(0);
    }
    int pon = val[node] - 1;
    mp[pon] -= cost[node];
    mp[pon + 1] += cost[node];
    while(mp[pon] <= 0){
        auto itr = prev(mp.find(pon));
        itr->se += mp[pon];
        mp.erase(pon);
        pon = itr->fi;
    }
    mp[0] = 0;
}

bool repag[maxN];

signed main(){
    // freopen(".inp", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for1(i, 1, n){
        cin >> a[i] >> val[i] >> cost[i];
        ++chi[a[i]];
        sum += cost[i];
    }
    memset(trigg, 1, sizeof(trigg));
    for1(i, 1, n) if(chi[i] == 0){
        int cop = i;
        while(chi[cop] == 0){
            trigg[cop] = 0;
            cop = a[cop];
            --chi[cop];
        }
    }
    for1(i, 1, n) par[i] = i;
    memset(repag, 0, sizeof(repag));
    for1(i, 1, n) if(trigg[i]){
        if(repag[i]) continue;
        vector<ii> cac; int cop = i;
        while(1){
            cac.pb(ii(val[cop], cop));
            cop = a[cop];
            repag[cop] = 1;
            // cout << cop << " " << i << endl;
            if(cop == i) break;
        }
        sort(all(cac));
        cac.pb(ii(0, 0));
        reverse(all(cac));
        for1(i, 1, (int)cac.size() - 1){
            x = cac[i - 1].se;
            y = cac[i].se;
            vc[x].pb(y);
            par[x] = y;
        }
    }
    for1(i, 1, n){
        if(!trigg[i]) vc[find(a[i])].pb(i);
    }
    map<int, int> mp;
    dfs(0, mp);
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Correct 3 ms 5332 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 8 ms 5916 KB Output is correct
6 Correct 7 ms 5716 KB Output is correct
7 Correct 7 ms 5716 KB Output is correct
8 Correct 8 ms 5972 KB Output is correct
9 Correct 7 ms 5756 KB Output is correct
10 Correct 8 ms 5716 KB Output is correct
11 Correct 6 ms 5736 KB Output is correct
12 Correct 8 ms 6996 KB Output is correct
13 Correct 6 ms 6944 KB Output is correct
14 Correct 8 ms 6356 KB Output is correct
15 Correct 7 ms 6356 KB Output is correct
16 Correct 9 ms 5972 KB Output is correct
17 Correct 7 ms 5716 KB Output is correct
18 Correct 7 ms 5588 KB Output is correct
19 Correct 9 ms 6356 KB Output is correct
20 Correct 6 ms 6236 KB Output is correct
21 Correct 7 ms 6228 KB Output is correct
22 Correct 6 ms 5844 KB Output is correct
23 Correct 5 ms 5588 KB Output is correct
24 Correct 8 ms 6484 KB Output is correct
25 Correct 7 ms 6284 KB Output is correct
26 Correct 6 ms 6932 KB Output is correct
27 Correct 6 ms 6228 KB Output is correct
28 Correct 8 ms 6480 KB Output is correct
29 Correct 7 ms 6740 KB Output is correct
30 Correct 7 ms 6740 KB Output is correct
31 Correct 8 ms 6704 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Correct 3 ms 5332 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 8 ms 5916 KB Output is correct
6 Correct 7 ms 5716 KB Output is correct
7 Correct 7 ms 5716 KB Output is correct
8 Correct 8 ms 5972 KB Output is correct
9 Correct 7 ms 5756 KB Output is correct
10 Correct 8 ms 5716 KB Output is correct
11 Correct 6 ms 5736 KB Output is correct
12 Correct 8 ms 6996 KB Output is correct
13 Correct 6 ms 6944 KB Output is correct
14 Correct 8 ms 6356 KB Output is correct
15 Correct 7 ms 6356 KB Output is correct
16 Correct 9 ms 5972 KB Output is correct
17 Correct 7 ms 5716 KB Output is correct
18 Correct 7 ms 5588 KB Output is correct
19 Correct 9 ms 6356 KB Output is correct
20 Correct 6 ms 6236 KB Output is correct
21 Correct 7 ms 6228 KB Output is correct
22 Correct 6 ms 5844 KB Output is correct
23 Correct 5 ms 5588 KB Output is correct
24 Correct 8 ms 6484 KB Output is correct
25 Correct 7 ms 6284 KB Output is correct
26 Correct 6 ms 6932 KB Output is correct
27 Correct 6 ms 6228 KB Output is correct
28 Correct 8 ms 6480 KB Output is correct
29 Correct 7 ms 6740 KB Output is correct
30 Correct 7 ms 6740 KB Output is correct
31 Correct 8 ms 6704 KB Output is correct
32 Correct 8 ms 5948 KB Output is correct
33 Correct 308 ms 29304 KB Output is correct
34 Correct 218 ms 17384 KB Output is correct
35 Correct 289 ms 27276 KB Output is correct
36 Correct 210 ms 17252 KB Output is correct
37 Correct 169 ms 16964 KB Output is correct
38 Correct 155 ms 16972 KB Output is correct
39 Correct 273 ms 69580 KB Output is correct
40 Correct 247 ms 69576 KB Output is correct
41 Correct 128 ms 69560 KB Output is correct
42 Correct 237 ms 44580 KB Output is correct
43 Correct 231 ms 44580 KB Output is correct
44 Correct 298 ms 27916 KB Output is correct
45 Correct 217 ms 16012 KB Output is correct
46 Correct 108 ms 15456 KB Output is correct
47 Correct 327 ms 41340 KB Output is correct
48 Correct 181 ms 40612 KB Output is correct
49 Correct 109 ms 40616 KB Output is correct
50 Correct 192 ms 25740 KB Output is correct
51 Correct 114 ms 13768 KB Output is correct
52 Correct 310 ms 47680 KB Output is correct
53 Correct 163 ms 41500 KB Output is correct
54 Correct 138 ms 69616 KB Output is correct
55 Correct 214 ms 44352 KB Output is correct
56 Correct 257 ms 55648 KB Output is correct
57 Correct 243 ms 60992 KB Output is correct
58 Correct 254 ms 57116 KB Output is correct
59 Correct 257 ms 56948 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Correct 3 ms 5332 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 8 ms 5916 KB Output is correct
6 Correct 7 ms 5716 KB Output is correct
7 Correct 7 ms 5716 KB Output is correct
8 Correct 8 ms 5972 KB Output is correct
9 Correct 7 ms 5756 KB Output is correct
10 Correct 8 ms 5716 KB Output is correct
11 Correct 6 ms 5736 KB Output is correct
12 Correct 8 ms 6996 KB Output is correct
13 Correct 6 ms 6944 KB Output is correct
14 Correct 8 ms 6356 KB Output is correct
15 Correct 7 ms 6356 KB Output is correct
16 Correct 9 ms 5972 KB Output is correct
17 Correct 7 ms 5716 KB Output is correct
18 Correct 7 ms 5588 KB Output is correct
19 Correct 9 ms 6356 KB Output is correct
20 Correct 6 ms 6236 KB Output is correct
21 Correct 7 ms 6228 KB Output is correct
22 Correct 6 ms 5844 KB Output is correct
23 Correct 5 ms 5588 KB Output is correct
24 Correct 8 ms 6484 KB Output is correct
25 Correct 7 ms 6284 KB Output is correct
26 Correct 6 ms 6932 KB Output is correct
27 Correct 6 ms 6228 KB Output is correct
28 Correct 8 ms 6480 KB Output is correct
29 Correct 7 ms 6740 KB Output is correct
30 Correct 7 ms 6740 KB Output is correct
31 Correct 8 ms 6704 KB Output is correct
32 Correct 8 ms 5948 KB Output is correct
33 Correct 308 ms 29304 KB Output is correct
34 Correct 218 ms 17384 KB Output is correct
35 Correct 289 ms 27276 KB Output is correct
36 Correct 210 ms 17252 KB Output is correct
37 Correct 169 ms 16964 KB Output is correct
38 Correct 155 ms 16972 KB Output is correct
39 Correct 273 ms 69580 KB Output is correct
40 Correct 247 ms 69576 KB Output is correct
41 Correct 128 ms 69560 KB Output is correct
42 Correct 237 ms 44580 KB Output is correct
43 Correct 231 ms 44580 KB Output is correct
44 Correct 298 ms 27916 KB Output is correct
45 Correct 217 ms 16012 KB Output is correct
46 Correct 108 ms 15456 KB Output is correct
47 Correct 327 ms 41340 KB Output is correct
48 Correct 181 ms 40612 KB Output is correct
49 Correct 109 ms 40616 KB Output is correct
50 Correct 192 ms 25740 KB Output is correct
51 Correct 114 ms 13768 KB Output is correct
52 Correct 310 ms 47680 KB Output is correct
53 Correct 163 ms 41500 KB Output is correct
54 Correct 138 ms 69616 KB Output is correct
55 Correct 214 ms 44352 KB Output is correct
56 Correct 257 ms 55648 KB Output is correct
57 Correct 243 ms 60992 KB Output is correct
58 Correct 254 ms 57116 KB Output is correct
59 Correct 257 ms 56948 KB Output is correct
60 Correct 3 ms 5332 KB Output is correct
61 Correct 3 ms 5332 KB Output is correct
62 Correct 4 ms 5332 KB Output is correct
63 Correct 3 ms 5420 KB Output is correct
64 Incorrect 114 ms 22588 KB Output isn't correct
65 Halted 0 ms 0 KB -