oj.uz

Submission #1034640

# Submission time Handle Problem Language Result Execution time Memory
1034640 2024-07-25T15:41:57 Z underwaterkillerwhale Worst Reporter 4 (JOI21_worst_reporter4) C++17
100 / 100
 329 ms 81844 KB 
#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const int szBL = 320;
const int  INF = 1e9;
const int BASE = 137;
struct Data {
    int A, H, C;
};
int n;
Data a[N];
int szC[N];
vector<int> ke[N];

map<int, ll> dp[N];///dp[u]: decreasing function

int dd[N], par[N];

void dfs (int u, vector<int> &Val) {
//    cout<< u <<"\n";
    if (!dd[u]) dd[u] = 1;
    Val.push_back(a[u].H);
    szC[u] = 1;
    int mxV = -1;
    iter (&v, ke[u]) {
        dfs(v, Val);
        szC[u] += szC[v];
        if (mxV == -1 || szC[mxV] < szC[v]) mxV = v;
    }
    if (mxV != -1) swap(dp[u], dp[mxV]);
    iter (&v, ke[u]) {
        if (v == mxV) continue;
        iter (&id, dp[v]) {
            dp[u][id.fs] += id.se;
        }
        map<int, ll> ().swap(dp[v]);
    }
    dp[u][a[u].H] += a[u].C;
    ll val = a[u].C;
    auto it = dp[u].lower_bound(a[u].H);
    while (it != dp[u].begin()) {
        --it;
        if (val >= it->se) {
            val -= it->se;
            it = dp[u].erase(it);
        }
        else {
            it->se -= val;
            break;
        }
    }
//    cout << u<<": ";
//    iter (&id, dp[u]) cout <<id.fs<<","<<id.se<<" ";
//    cout<<"\n";
}

void solution () {
    cin >> n;
    ll tot = 0;
    rep (i, 1, n) {
        cin >> a[i].A >> a[i].H >> a[i].C;
        tot += a[i].C;
        ke[a[i].A].push_back(i);
        par[i] = a[i].A;
//        cout << a[i].A <<" "<<i<<" h\n";
    }
    ll res = 0;
    rep (u, 1, n) {
        if (dd[u]) continue;
        static vector<int> ver; ver.clear();
        int cur = u;
        while (!dd[cur]) {
            dd[cur] = 1;
            ver.push_back(cur);
            cur = par[cur];
        }
        vector<int> cycle (find(ALL(ver), cur), ver.end());
        iter (&v, cycle) dd[v] = 2;
        static map<int, ll> dpr, cnt; dpr.clear(); cnt.clear();
        static vector<int> Val; Val.clear();
        iter (&v, cycle) {
//            cout << v<<"\n";
            cnt[a[v].H] += a[v].C;
            Val.push_back(a[v].H);
            iter (&k, ke[v]) {
                if (dd[k] == 2) continue;
                dfs(k, Val);
                if (SZ(dp[k]) > SZ(dpr)) swap(dpr, dp[k]);
                iter (&id, dp[k]) {
                    dpr[id.fs] += id.se;
                }
            }
        }
        dpr[INF] += 0;
        for (auto it = dpr.rbegin(); ; ++it) {
            if (next(it) == dpr.rend()) break;
            next(it)->se += it->se;
//            cout << it->fs <<" "<<it->se <<"\n";
        }
        ll delta = 0;
        iter (&id, Val) {
            delta = max(delta, cnt[id] + dpr.lower_bound(id)->se);
        }
        res += delta;
//        cout<<"\n";
    }
    cout << tot - res <<"\n";
}

#define file(name) freopen(name".inp", "r", stdin); \
freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
no bug challenge

*/

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 6 ms 14564 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 11 ms 15416 KB Output is correct
6 Correct 9 ms 14940 KB Output is correct
7 Correct 8 ms 14700 KB Output is correct
8 Correct 10 ms 15452 KB Output is correct
9 Correct 11 ms 14844 KB Output is correct
10 Correct 7 ms 14936 KB Output is correct
11 Correct 7 ms 14940 KB Output is correct
12 Correct 8 ms 15964 KB Output is correct
13 Correct 7 ms 15752 KB Output is correct
14 Correct 8 ms 15708 KB Output is correct
15 Correct 8 ms 15196 KB Output is correct
16 Correct 10 ms 15452 KB Output is correct
17 Correct 8 ms 14936 KB Output is correct
18 Correct 7 ms 14940 KB Output is correct
19 Correct 8 ms 15708 KB Output is correct
20 Correct 7 ms 15196 KB Output is correct
21 Correct 7 ms 15364 KB Output is correct
22 Correct 9 ms 15704 KB Output is correct
23 Correct 7 ms 14940 KB Output is correct
24 Correct 11 ms 15704 KB Output is correct
25 Correct 8 ms 15452 KB Output is correct
26 Correct 8 ms 15964 KB Output is correct
27 Correct 9 ms 15616 KB Output is correct
28 Correct 8 ms 15972 KB Output is correct
29 Correct 8 ms 15964 KB Output is correct
30 Correct 9 ms 15960 KB Output is correct
31 Correct 10 ms 15964 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 6 ms 14564 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 11 ms 15416 KB Output is correct
6 Correct 9 ms 14940 KB Output is correct
7 Correct 8 ms 14700 KB Output is correct
8 Correct 10 ms 15452 KB Output is correct
9 Correct 11 ms 14844 KB Output is correct
10 Correct 7 ms 14936 KB Output is correct
11 Correct 7 ms 14940 KB Output is correct
12 Correct 8 ms 15964 KB Output is correct
13 Correct 7 ms 15752 KB Output is correct
14 Correct 8 ms 15708 KB Output is correct
15 Correct 8 ms 15196 KB Output is correct
16 Correct 10 ms 15452 KB Output is correct
17 Correct 8 ms 14936 KB Output is correct
18 Correct 7 ms 14940 KB Output is correct
19 Correct 8 ms 15708 KB Output is correct
20 Correct 7 ms 15196 KB Output is correct
21 Correct 7 ms 15364 KB Output is correct
22 Correct 9 ms 15704 KB Output is correct
23 Correct 7 ms 14940 KB Output is correct
24 Correct 11 ms 15704 KB Output is correct
25 Correct 8 ms 15452 KB Output is correct
26 Correct 8 ms 15964 KB Output is correct
27 Correct 9 ms 15616 KB Output is correct
28 Correct 8 ms 15972 KB Output is correct
29 Correct 8 ms 15964 KB Output is correct
30 Correct 9 ms 15960 KB Output is correct
31 Correct 10 ms 15964 KB Output is correct
32 Correct 10 ms 15452 KB Output is correct
33 Correct 320 ms 55908 KB Output is correct
34 Correct 142 ms 28876 KB Output is correct
35 Correct 313 ms 54520 KB Output is correct
36 Correct 165 ms 28924 KB Output is correct
37 Correct 93 ms 28556 KB Output is correct
38 Correct 80 ms 28368 KB Output is correct
39 Correct 219 ms 78320 KB Output is correct
40 Correct 119 ms 65932 KB Output is correct
41 Correct 81 ms 65988 KB Output is correct
42 Correct 165 ms 61120 KB Output is correct
43 Correct 108 ms 48696 KB Output is correct
44 Correct 303 ms 52928 KB Output is correct
45 Correct 143 ms 28444 KB Output is correct
46 Correct 58 ms 28108 KB Output is correct
47 Correct 280 ms 64964 KB Output is correct
48 Correct 93 ms 45400 KB Output is correct
49 Correct 70 ms 45512 KB Output is correct
50 Correct 317 ms 62412 KB Output is correct
51 Correct 80 ms 37584 KB Output is correct
52 Correct 329 ms 65332 KB Output is correct
53 Correct 94 ms 52036 KB Output is correct
54 Correct 111 ms 78484 KB Output is correct
55 Correct 193 ms 66300 KB Output is correct
56 Correct 157 ms 77000 KB Output is correct
57 Correct 159 ms 81844 KB Output is correct
58 Correct 208 ms 79048 KB Output is correct
59 Correct 184 ms 79200 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 6 ms 14564 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 11 ms 15416 KB Output is correct
6 Correct 9 ms 14940 KB Output is correct
7 Correct 8 ms 14700 KB Output is correct
8 Correct 10 ms 15452 KB Output is correct
9 Correct 11 ms 14844 KB Output is correct
10 Correct 7 ms 14936 KB Output is correct
11 Correct 7 ms 14940 KB Output is correct
12 Correct 8 ms 15964 KB Output is correct
13 Correct 7 ms 15752 KB Output is correct
14 Correct 8 ms 15708 KB Output is correct
15 Correct 8 ms 15196 KB Output is correct
16 Correct 10 ms 15452 KB Output is correct
17 Correct 8 ms 14936 KB Output is correct
18 Correct 7 ms 14940 KB Output is correct
19 Correct 8 ms 15708 KB Output is correct
20 Correct 7 ms 15196 KB Output is correct
21 Correct 7 ms 15364 KB Output is correct
22 Correct 9 ms 15704 KB Output is correct
23 Correct 7 ms 14940 KB Output is correct
24 Correct 11 ms 15704 KB Output is correct
25 Correct 8 ms 15452 KB Output is correct
26 Correct 8 ms 15964 KB Output is correct
27 Correct 9 ms 15616 KB Output is correct
28 Correct 8 ms 15972 KB Output is correct
29 Correct 8 ms 15964 KB Output is correct
30 Correct 9 ms 15960 KB Output is correct
31 Correct 10 ms 15964 KB Output is correct
32 Correct 10 ms 15452 KB Output is correct
33 Correct 320 ms 55908 KB Output is correct
34 Correct 142 ms 28876 KB Output is correct
35 Correct 313 ms 54520 KB Output is correct
36 Correct 165 ms 28924 KB Output is correct
37 Correct 93 ms 28556 KB Output is correct
38 Correct 80 ms 28368 KB Output is correct
39 Correct 219 ms 78320 KB Output is correct
40 Correct 119 ms 65932 KB Output is correct
41 Correct 81 ms 65988 KB Output is correct
42 Correct 165 ms 61120 KB Output is correct
43 Correct 108 ms 48696 KB Output is correct
44 Correct 303 ms 52928 KB Output is correct
45 Correct 143 ms 28444 KB Output is correct
46 Correct 58 ms 28108 KB Output is correct
47 Correct 280 ms 64964 KB Output is correct
48 Correct 93 ms 45400 KB Output is correct
49 Correct 70 ms 45512 KB Output is correct
50 Correct 317 ms 62412 KB Output is correct
51 Correct 80 ms 37584 KB Output is correct
52 Correct 329 ms 65332 KB Output is correct
53 Correct 94 ms 52036 KB Output is correct
54 Correct 111 ms 78484 KB Output is correct
55 Correct 193 ms 66300 KB Output is correct
56 Correct 157 ms 77000 KB Output is correct
57 Correct 159 ms 81844 KB Output is correct
58 Correct 208 ms 79048 KB Output is correct
59 Correct 184 ms 79200 KB Output is correct
60 Correct 6 ms 14428 KB Output is correct
61 Correct 5 ms 14428 KB Output is correct
62 Correct 7 ms 14684 KB Output is correct
63 Correct 5 ms 14400 KB Output is correct
64 Correct 316 ms 50292 KB Output is correct
65 Correct 139 ms 29988 KB Output is correct
66 Correct 298 ms 50628 KB Output is correct
67 Correct 143 ms 30664 KB Output is correct
68 Correct 91 ms 29748 KB Output is correct
69 Correct 89 ms 28768 KB Output is correct
70 Correct 176 ms 40156 KB Output is correct
71 Correct 87 ms 31428 KB Output is correct
72 Correct 181 ms 44676 KB Output is correct
73 Correct 93 ms 32968 KB Output is correct
74 Correct 309 ms 53956 KB Output is correct
75 Correct 118 ms 35268 KB Output is correct
76 Correct 105 ms 35248 KB Output is correct
77 Correct 243 ms 54344 KB Output is correct
78 Correct 93 ms 35920 KB Output is correct
79 Correct 281 ms 50392 KB Output is correct
80 Correct 122 ms 31828 KB Output is correct
81 Correct 85 ms 31016 KB Output is correct
82 Correct 122 ms 44860 KB Output is correct
83 Correct 71 ms 29644 KB Output is correct
84 Correct 239 ms 57288 KB Output is correct
85 Correct 208 ms 57288 KB Output is correct
86 Correct 218 ms 54216 KB Output is correct
87 Correct 222 ms 57472 KB Output is correct
88 Correct 222 ms 57428 KB Output is correct