oj.uz

Submission #1059124

# Submission time Handle Problem Language Result Execution time Memory
1059124 2024-08-14T17:33:16 Z Tonyl Jobs (BOI24_jobs) C++17
100 / 100
 241 ms 83908 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
using vi = vector<int>;
using pi = pair<ll,ll>;
#define REP(i,n) for (int i = 0; i < n; i++)
#define trav(a,x) for (auto& a : x)
#define D(x) //cerr << #x << ": " << x << endl;
#define all(x) (x).begin(), (x).end()
const int MAX_N = 3*1e5+3;

struct Info {
    map<ll, ll> rew;

    void add(int r) {
        if (r == 0) return;
        if (r > 0) {
            rew[0] += r;
        } else {
            r*=-1;
            ll rr = r;
            //off += r;
            // go erasing

            while (rew.size() && rr) {
                if (rew.begin()->second > rr) {
                    rew.begin()->second -= rr;
                    rr = 0;
                } else {
                    rr -= rew.begin()->second;
                    rew.erase(rew.begin());
                    r = rr;
                }
            }

            if (rew.size() == 0) return;
            // move
            ll stole = 0;
            ll bef = 0;
            while (rew.size() && stole == 0) {
                bef = rew.begin()->first;
                stole += rew.begin()->second;
                rew.erase(rew.begin());
            }
            bef += r;
            while (rew.size() && rew.begin()->first < bef) {
                stole += rew.begin()->second;
                rew.erase(rew.begin());
            }
            assert(stole > 0);
            rew[bef] += stole;
        }
    }

    void merge(Info* other) {
        trav(o, other->rew) {
            ll re = o.first;
            rew[re] += o.second;
        }
        delete other;
    }

    ~Info() {
        rew.clear();
    }
};

int n; ll s;
vi children[MAX_N];
int values[MAX_N];
bool done[MAX_N];

Info* dfs(int i) {
    done[i] = 1;

    Info* info = new Info;
    trav(ch, children[i]) {
        Info* other = dfs(ch);
        if (info->rew.size() < other->rew.size()) swap(info, other);
        info->merge(other);
    }
    info->add(values[i]);
    return info;
}

ll triv_dfs(int i) {
    done[i] = 1;
    ll tot = values[i];
    trav(ch, children[i]) tot += triv_dfs(ch);
    return max(tot, 0ll);
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    priority_queue<pi, vector<pi>, greater<pi>> q;

    cin >> n >> s;
    ll ss = s;

    REP(i,n) {
        int p; cin >> values[i] >> p;
        if (p == 0) continue;
        p--;

        children[p].push_back(i);
    }

    REP(i,n) {
        if (done[i]) continue;
        Info* info = dfs(i);
        trav(r, info->rew) {
            q.push({r.first, r.second});
        }
    }

    while (q.size()) {
        auto r = q.top(); q.pop();
        D(r.first);
        D(r.second);
        if (r.first <= s) s += r.second;
        assert(r.second > 0);
        //else break;
    }

    assert(s >= ss);
    cout << s - ss << endl;
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 33616 KB Output is correct
2 Correct 112 ms 33984 KB Output is correct
3 Correct 91 ms 37568 KB Output is correct
4 Correct 94 ms 45520 KB Output is correct
5 Correct 104 ms 54956 KB Output is correct
6 Correct 94 ms 21844 KB Output is correct
7 Correct 179 ms 34504 KB Output is correct
8 Correct 95 ms 38288 KB Output is correct
9 Correct 89 ms 49744 KB Output is correct
10 Correct 86 ms 54720 KB Output is correct
11 Correct 232 ms 37184 KB Output is correct
12 Correct 144 ms 30532 KB Output is correct
13 Correct 181 ms 30184 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7852 KB Output is correct
2 Correct 2 ms 7860 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 3 ms 8028 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 2 ms 8028 KB Output is correct
7 Correct 3 ms 8028 KB Output is correct
8 Correct 3 ms 8028 KB Output is correct
9 Correct 3 ms 8028 KB Output is correct
10 Correct 3 ms 7988 KB Output is correct
11 Correct 3 ms 8264 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 3 ms 8028 KB Output is correct
14 Correct 3 ms 8028 KB Output is correct
15 Correct 3 ms 8028 KB Output is correct
16 Correct 3 ms 8112 KB Output is correct
17 Correct 3 ms 8284 KB Output is correct
18 Correct 3 ms 8188 KB Output is correct
19 Correct 3 ms 8172 KB Output is correct
20 Correct 3 ms 8028 KB Output is correct
21 Correct 2 ms 8028 KB Output is correct
22 Correct 2 ms 8028 KB Output is correct
23 Correct 4 ms 8264 KB Output is correct
24 Correct 2 ms 8284 KB Output is correct
25 Correct 3 ms 7932 KB Output is correct
26 Correct 2 ms 7928 KB Output is correct
27 Correct 4 ms 8028 KB Output is correct
28 Correct 2 ms 8028 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7852 KB Output is correct
2 Correct 2 ms 7860 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 3 ms 8028 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 2 ms 8028 KB Output is correct
7 Correct 3 ms 8028 KB Output is correct
8 Correct 3 ms 8028 KB Output is correct
9 Correct 3 ms 8028 KB Output is correct
10 Correct 3 ms 7988 KB Output is correct
11 Correct 3 ms 8264 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 3 ms 8028 KB Output is correct
14 Correct 3 ms 8028 KB Output is correct
15 Correct 3 ms 8028 KB Output is correct
16 Correct 3 ms 8112 KB Output is correct
17 Correct 3 ms 8284 KB Output is correct
18 Correct 3 ms 8188 KB Output is correct
19 Correct 3 ms 8172 KB Output is correct
20 Correct 3 ms 8028 KB Output is correct
21 Correct 2 ms 8028 KB Output is correct
22 Correct 2 ms 8028 KB Output is correct
23 Correct 4 ms 8264 KB Output is correct
24 Correct 2 ms 8284 KB Output is correct
25 Correct 3 ms 7932 KB Output is correct
26 Correct 2 ms 7928 KB Output is correct
27 Correct 4 ms 8028 KB Output is correct
28 Correct 2 ms 8028 KB Output is correct
29 Correct 77 ms 35772 KB Output is correct
30 Correct 73 ms 36308 KB Output is correct
31 Correct 75 ms 39060 KB Output is correct
32 Correct 110 ms 80312 KB Output is correct
33 Correct 109 ms 60620 KB Output is correct
34 Correct 86 ms 46976 KB Output is correct
35 Correct 36 ms 21084 KB Output is correct
36 Correct 88 ms 40692 KB Output is correct
37 Correct 78 ms 36804 KB Output is correct
38 Correct 102 ms 81796 KB Output is correct
39 Correct 108 ms 62388 KB Output is correct
40 Correct 93 ms 45388 KB Output is correct
41 Correct 89 ms 34432 KB Output is correct
42 Correct 34 ms 27092 KB Output is correct
43 Correct 105 ms 48588 KB Output is correct
44 Correct 114 ms 83868 KB Output is correct
45 Correct 109 ms 62052 KB Output is correct
46 Correct 95 ms 47872 KB Output is correct
47 Correct 90 ms 34332 KB Output is correct
48 Correct 76 ms 38608 KB Output is correct
49 Correct 94 ms 36452 KB Output is correct
50 Correct 121 ms 83832 KB Output is correct
51 Correct 73 ms 48244 KB Output is correct
52 Correct 108 ms 44956 KB Output is correct
53 Correct 62 ms 35248 KB Output is correct
54 Correct 69 ms 37832 KB Output is correct
55 Correct 90 ms 36676 KB Output is correct
56 Correct 101 ms 83908 KB Output is correct
57 Correct 141 ms 60608 KB Output is correct
58 Correct 90 ms 44784 KB Output is correct
59 Correct 75 ms 42400 KB Output is correct
60 Correct 66 ms 37824 KB Output is correct
61 Correct 78 ms 43336 KB Output is correct
62 Correct 98 ms 47296 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7852 KB Output is correct
2 Correct 2 ms 7860 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 3 ms 8028 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 2 ms 8028 KB Output is correct
7 Correct 3 ms 8028 KB Output is correct
8 Correct 3 ms 8028 KB Output is correct
9 Correct 3 ms 8028 KB Output is correct
10 Correct 3 ms 7988 KB Output is correct
11 Correct 3 ms 8264 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 3 ms 8028 KB Output is correct
14 Correct 3 ms 8028 KB Output is correct
15 Correct 3 ms 8028 KB Output is correct
16 Correct 3 ms 8112 KB Output is correct
17 Correct 3 ms 8284 KB Output is correct
18 Correct 3 ms 8188 KB Output is correct
19 Correct 3 ms 8172 KB Output is correct
20 Correct 3 ms 8028 KB Output is correct
21 Correct 2 ms 8028 KB Output is correct
22 Correct 2 ms 8028 KB Output is correct
23 Correct 4 ms 8264 KB Output is correct
24 Correct 2 ms 8284 KB Output is correct
25 Correct 3 ms 7932 KB Output is correct
26 Correct 2 ms 7928 KB Output is correct
27 Correct 4 ms 8028 KB Output is correct
28 Correct 2 ms 8028 KB Output is correct
29 Correct 2 ms 7772 KB Output is correct
30 Correct 3 ms 8028 KB Output is correct
31 Correct 2 ms 8028 KB Output is correct
32 Correct 2 ms 8028 KB Output is correct
33 Correct 2 ms 8028 KB Output is correct
34 Correct 2 ms 8028 KB Output is correct
35 Correct 2 ms 8028 KB Output is correct
36 Correct 3 ms 8116 KB Output is correct
37 Correct 3 ms 8028 KB Output is correct
38 Correct 3 ms 8028 KB Output is correct
39 Correct 3 ms 8028 KB Output is correct
40 Correct 2 ms 8028 KB Output is correct
41 Correct 3 ms 8104 KB Output is correct
42 Correct 3 ms 8028 KB Output is correct
43 Correct 3 ms 8024 KB Output is correct
44 Correct 3 ms 8024 KB Output is correct
45 Correct 2 ms 7856 KB Output is correct
46 Correct 2 ms 8028 KB Output is correct
47 Correct 2 ms 8028 KB Output is correct
48 Correct 3 ms 8028 KB Output is correct
49 Correct 2 ms 8116 KB Output is correct
50 Correct 3 ms 8028 KB Output is correct
51 Correct 3 ms 8024 KB Output is correct
52 Correct 2 ms 8024 KB Output is correct
53 Correct 3 ms 8028 KB Output is correct
54 Correct 2 ms 8028 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 33616 KB Output is correct
2 Correct 112 ms 33984 KB Output is correct
3 Correct 91 ms 37568 KB Output is correct
4 Correct 94 ms 45520 KB Output is correct
5 Correct 104 ms 54956 KB Output is correct
6 Correct 94 ms 21844 KB Output is correct
7 Correct 179 ms 34504 KB Output is correct
8 Correct 95 ms 38288 KB Output is correct
9 Correct 89 ms 49744 KB Output is correct
10 Correct 86 ms 54720 KB Output is correct
11 Correct 232 ms 37184 KB Output is correct
12 Correct 144 ms 30532 KB Output is correct
13 Correct 181 ms 30184 KB Output is correct
14 Correct 3 ms 7852 KB Output is correct
15 Correct 2 ms 7860 KB Output is correct
16 Correct 2 ms 7772 KB Output is correct
17 Correct 3 ms 8028 KB Output is correct
18 Correct 4 ms 8284 KB Output is correct
19 Correct 2 ms 8028 KB Output is correct
20 Correct 3 ms 8028 KB Output is correct
21 Correct 3 ms 8028 KB Output is correct
22 Correct 3 ms 8028 KB Output is correct
23 Correct 3 ms 7988 KB Output is correct
24 Correct 3 ms 8264 KB Output is correct
25 Correct 2 ms 8028 KB Output is correct
26 Correct 3 ms 8028 KB Output is correct
27 Correct 3 ms 8028 KB Output is correct
28 Correct 3 ms 8028 KB Output is correct
29 Correct 3 ms 8112 KB Output is correct
30 Correct 3 ms 8284 KB Output is correct
31 Correct 3 ms 8188 KB Output is correct
32 Correct 3 ms 8172 KB Output is correct
33 Correct 3 ms 8028 KB Output is correct
34 Correct 2 ms 8028 KB Output is correct
35 Correct 2 ms 8028 KB Output is correct
36 Correct 4 ms 8264 KB Output is correct
37 Correct 2 ms 8284 KB Output is correct
38 Correct 3 ms 7932 KB Output is correct
39 Correct 2 ms 7928 KB Output is correct
40 Correct 4 ms 8028 KB Output is correct
41 Correct 2 ms 8028 KB Output is correct
42 Correct 77 ms 35772 KB Output is correct
43 Correct 73 ms 36308 KB Output is correct
44 Correct 75 ms 39060 KB Output is correct
45 Correct 110 ms 80312 KB Output is correct
46 Correct 109 ms 60620 KB Output is correct
47 Correct 86 ms 46976 KB Output is correct
48 Correct 36 ms 21084 KB Output is correct
49 Correct 88 ms 40692 KB Output is correct
50 Correct 78 ms 36804 KB Output is correct
51 Correct 102 ms 81796 KB Output is correct
52 Correct 108 ms 62388 KB Output is correct
53 Correct 93 ms 45388 KB Output is correct
54 Correct 89 ms 34432 KB Output is correct
55 Correct 34 ms 27092 KB Output is correct
56 Correct 105 ms 48588 KB Output is correct
57 Correct 114 ms 83868 KB Output is correct
58 Correct 109 ms 62052 KB Output is correct
59 Correct 95 ms 47872 KB Output is correct
60 Correct 90 ms 34332 KB Output is correct
61 Correct 76 ms 38608 KB Output is correct
62 Correct 94 ms 36452 KB Output is correct
63 Correct 121 ms 83832 KB Output is correct
64 Correct 73 ms 48244 KB Output is correct
65 Correct 108 ms 44956 KB Output is correct
66 Correct 62 ms 35248 KB Output is correct
67 Correct 69 ms 37832 KB Output is correct
68 Correct 90 ms 36676 KB Output is correct
69 Correct 101 ms 83908 KB Output is correct
70 Correct 141 ms 60608 KB Output is correct
71 Correct 90 ms 44784 KB Output is correct
72 Correct 75 ms 42400 KB Output is correct
73 Correct 66 ms 37824 KB Output is correct
74 Correct 78 ms 43336 KB Output is correct
75 Correct 98 ms 47296 KB Output is correct
76 Correct 2 ms 7772 KB Output is correct
77 Correct 3 ms 8028 KB Output is correct
78 Correct 2 ms 8028 KB Output is correct
79 Correct 2 ms 8028 KB Output is correct
80 Correct 2 ms 8028 KB Output is correct
81 Correct 2 ms 8028 KB Output is correct
82 Correct 2 ms 8028 KB Output is correct
83 Correct 3 ms 8116 KB Output is correct
84 Correct 3 ms 8028 KB Output is correct
85 Correct 3 ms 8028 KB Output is correct
86 Correct 3 ms 8028 KB Output is correct
87 Correct 2 ms 8028 KB Output is correct
88 Correct 3 ms 8104 KB Output is correct
89 Correct 3 ms 8028 KB Output is correct
90 Correct 3 ms 8024 KB Output is correct
91 Correct 3 ms 8024 KB Output is correct
92 Correct 2 ms 7856 KB Output is correct
93 Correct 2 ms 8028 KB Output is correct
94 Correct 2 ms 8028 KB Output is correct
95 Correct 3 ms 8028 KB Output is correct
96 Correct 2 ms 8116 KB Output is correct
97 Correct 3 ms 8028 KB Output is correct
98 Correct 3 ms 8024 KB Output is correct
99 Correct 2 ms 8024 KB Output is correct
100 Correct 3 ms 8028 KB Output is correct
101 Correct 2 ms 8028 KB Output is correct
102 Correct 153 ms 35300 KB Output is correct
103 Correct 150 ms 33764 KB Output is correct
104 Correct 88 ms 30944 KB Output is correct
105 Correct 90 ms 38136 KB Output is correct
106 Correct 102 ms 55692 KB Output is correct
107 Correct 77 ms 45284 KB Output is correct
108 Correct 199 ms 34128 KB Output is correct
109 Correct 60 ms 19420 KB Output is correct
110 Correct 145 ms 28936 KB Output is correct
111 Correct 122 ms 31496 KB Output is correct
112 Correct 96 ms 32956 KB Output is correct
113 Correct 111 ms 43516 KB Output is correct
114 Correct 92 ms 56812 KB Output is correct
115 Correct 72 ms 19876 KB Output is correct
116 Correct 196 ms 35808 KB Output is correct
117 Correct 146 ms 29288 KB Output is correct
118 Correct 147 ms 30276 KB Output is correct
119 Correct 113 ms 34020 KB Output is correct
120 Correct 107 ms 45904 KB Output is correct
121 Correct 88 ms 44024 KB Output is correct
122 Correct 222 ms 38060 KB Output is correct
123 Correct 172 ms 35812 KB Output is correct
124 Correct 114 ms 30168 KB Output is correct
125 Correct 145 ms 30144 KB Output is correct
126 Correct 120 ms 38456 KB Output is correct
127 Correct 51 ms 25412 KB Output is correct
128 Correct 34 ms 25804 KB Output is correct
129 Correct 241 ms 37268 KB Output is correct
130 Correct 159 ms 34836 KB Output is correct
131 Correct 140 ms 34448 KB Output is correct
132 Correct 121 ms 29124 KB Output is correct
133 Correct 80 ms 37564 KB Output is correct
134 Correct 112 ms 56004 KB Output is correct
135 Correct 82 ms 49612 KB Output is correct
136 Correct 182 ms 37188 KB Output is correct
137 Correct 177 ms 38220 KB Output is correct