oj.uz

Submission #733085

# Submission time Handle Problem Language Result Execution time Memory
733085 2023-04-30T04:49:11 Z baokhue232005 Worst Reporter 4 (JOI21_worst_reporter4) C++14
79 / 100
 387 ms 69960 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;
        }
        cac.pb(ii(0, 0));
        sort(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 4 ms 5332 KB Output is correct
2 Correct 5 ms 5436 KB Output is correct
3 Correct 3 ms 5332 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 9 ms 6072 KB Output is correct
6 Correct 7 ms 5816 KB Output is correct
7 Correct 6 ms 5824 KB Output is correct
8 Correct 9 ms 6100 KB Output is correct
9 Correct 7 ms 5844 KB Output is correct
10 Correct 7 ms 5844 KB Output is correct
11 Correct 6 ms 5816 KB Output is correct
12 Correct 9 ms 7124 KB Output is correct
13 Correct 6 ms 7124 KB Output is correct
14 Correct 9 ms 6464 KB Output is correct
15 Correct 8 ms 6460 KB Output is correct
16 Correct 9 ms 6100 KB Output is correct
17 Correct 8 ms 5844 KB Output is correct
18 Correct 6 ms 5716 KB Output is correct
19 Correct 9 ms 6452 KB Output is correct
20 Correct 7 ms 6328 KB Output is correct
21 Correct 7 ms 6444 KB Output is correct
22 Correct 7 ms 5944 KB Output is correct
23 Correct 5 ms 5716 KB Output is correct
24 Correct 11 ms 6592 KB Output is correct
25 Correct 8 ms 6452 KB Output is correct
26 Correct 7 ms 7108 KB Output is correct
27 Correct 7 ms 6356 KB Output is correct
28 Correct 8 ms 6612 KB Output is correct
29 Correct 7 ms 6740 KB Output is correct
30 Correct 8 ms 6740 KB Output is correct
31 Correct 8 ms 6752 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB Output is correct
2 Correct 5 ms 5436 KB Output is correct
3 Correct 3 ms 5332 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 9 ms 6072 KB Output is correct
6 Correct 7 ms 5816 KB Output is correct
7 Correct 6 ms 5824 KB Output is correct
8 Correct 9 ms 6100 KB Output is correct
9 Correct 7 ms 5844 KB Output is correct
10 Correct 7 ms 5844 KB Output is correct
11 Correct 6 ms 5816 KB Output is correct
12 Correct 9 ms 7124 KB Output is correct
13 Correct 6 ms 7124 KB Output is correct
14 Correct 9 ms 6464 KB Output is correct
15 Correct 8 ms 6460 KB Output is correct
16 Correct 9 ms 6100 KB Output is correct
17 Correct 8 ms 5844 KB Output is correct
18 Correct 6 ms 5716 KB Output is correct
19 Correct 9 ms 6452 KB Output is correct
20 Correct 7 ms 6328 KB Output is correct
21 Correct 7 ms 6444 KB Output is correct
22 Correct 7 ms 5944 KB Output is correct
23 Correct 5 ms 5716 KB Output is correct
24 Correct 11 ms 6592 KB Output is correct
25 Correct 8 ms 6452 KB Output is correct
26 Correct 7 ms 7108 KB Output is correct
27 Correct 7 ms 6356 KB Output is correct
28 Correct 8 ms 6612 KB Output is correct
29 Correct 7 ms 6740 KB Output is correct
30 Correct 8 ms 6740 KB Output is correct
31 Correct 8 ms 6752 KB Output is correct
32 Correct 8 ms 5964 KB Output is correct
33 Correct 310 ms 29664 KB Output is correct
34 Correct 224 ms 17768 KB Output is correct
35 Correct 286 ms 27524 KB Output is correct
36 Correct 219 ms 17608 KB Output is correct
37 Correct 166 ms 17352 KB Output is correct
38 Correct 146 ms 17260 KB Output is correct
39 Correct 262 ms 69932 KB Output is correct
40 Correct 230 ms 69960 KB Output is correct
41 Correct 147 ms 69856 KB Output is correct
42 Correct 244 ms 44972 KB Output is correct
43 Correct 220 ms 44912 KB Output is correct
44 Correct 270 ms 28232 KB Output is correct
45 Correct 187 ms 16456 KB Output is correct
46 Correct 93 ms 15948 KB Output is correct
47 Correct 387 ms 41680 KB Output is correct
48 Correct 159 ms 40880 KB Output is correct
49 Correct 111 ms 40884 KB Output is correct
50 Correct 194 ms 26124 KB Output is correct
51 Correct 97 ms 14152 KB Output is correct
52 Correct 290 ms 48020 KB Output is correct
53 Correct 153 ms 41868 KB Output is correct
54 Correct 128 ms 69856 KB Output is correct
55 Correct 210 ms 44820 KB Output is correct
56 Correct 229 ms 56012 KB Output is correct
57 Correct 209 ms 61340 KB Output is correct
58 Correct 260 ms 57444 KB Output is correct
59 Correct 269 ms 57464 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB Output is correct
2 Correct 5 ms 5436 KB Output is correct
3 Correct 3 ms 5332 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 9 ms 6072 KB Output is correct
6 Correct 7 ms 5816 KB Output is correct
7 Correct 6 ms 5824 KB Output is correct
8 Correct 9 ms 6100 KB Output is correct
9 Correct 7 ms 5844 KB Output is correct
10 Correct 7 ms 5844 KB Output is correct
11 Correct 6 ms 5816 KB Output is correct
12 Correct 9 ms 7124 KB Output is correct
13 Correct 6 ms 7124 KB Output is correct
14 Correct 9 ms 6464 KB Output is correct
15 Correct 8 ms 6460 KB Output is correct
16 Correct 9 ms 6100 KB Output is correct
17 Correct 8 ms 5844 KB Output is correct
18 Correct 6 ms 5716 KB Output is correct
19 Correct 9 ms 6452 KB Output is correct
20 Correct 7 ms 6328 KB Output is correct
21 Correct 7 ms 6444 KB Output is correct
22 Correct 7 ms 5944 KB Output is correct
23 Correct 5 ms 5716 KB Output is correct
24 Correct 11 ms 6592 KB Output is correct
25 Correct 8 ms 6452 KB Output is correct
26 Correct 7 ms 7108 KB Output is correct
27 Correct 7 ms 6356 KB Output is correct
28 Correct 8 ms 6612 KB Output is correct
29 Correct 7 ms 6740 KB Output is correct
30 Correct 8 ms 6740 KB Output is correct
31 Correct 8 ms 6752 KB Output is correct
32 Correct 8 ms 5964 KB Output is correct
33 Correct 310 ms 29664 KB Output is correct
34 Correct 224 ms 17768 KB Output is correct
35 Correct 286 ms 27524 KB Output is correct
36 Correct 219 ms 17608 KB Output is correct
37 Correct 166 ms 17352 KB Output is correct
38 Correct 146 ms 17260 KB Output is correct
39 Correct 262 ms 69932 KB Output is correct
40 Correct 230 ms 69960 KB Output is correct
41 Correct 147 ms 69856 KB Output is correct
42 Correct 244 ms 44972 KB Output is correct
43 Correct 220 ms 44912 KB Output is correct
44 Correct 270 ms 28232 KB Output is correct
45 Correct 187 ms 16456 KB Output is correct
46 Correct 93 ms 15948 KB Output is correct
47 Correct 387 ms 41680 KB Output is correct
48 Correct 159 ms 40880 KB Output is correct
49 Correct 111 ms 40884 KB Output is correct
50 Correct 194 ms 26124 KB Output is correct
51 Correct 97 ms 14152 KB Output is correct
52 Correct 290 ms 48020 KB Output is correct
53 Correct 153 ms 41868 KB Output is correct
54 Correct 128 ms 69856 KB Output is correct
55 Correct 210 ms 44820 KB Output is correct
56 Correct 229 ms 56012 KB Output is correct
57 Correct 209 ms 61340 KB Output is correct
58 Correct 260 ms 57444 KB Output is correct
59 Correct 269 ms 57464 KB Output is correct
60 Incorrect 3 ms 5332 KB Output isn't correct
61 Halted 0 ms 0 KB -