QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#623713 | #8707. Jobs | Dimash# | 11 | 239ms | 268820kb | C++23 | 1.7kb | 2024-10-09 13:48:19 | 2024-10-09 13:48:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 12, MOD = (int)1e9 + 7;
#define int ll
int n, p[N], x[N];
ll s, d[N];
vector<int> g[N], rt, ord[N];
multiset<pair<ll, ll>> st[N];
void prec(int v) {
d[v] = x[v];
for(int to:g[v]) {
prec(to);
if(d[to] < 0) continue;
d[v] += d[to];
}
}
deque<pair<ll, ll>> deq[N];
void dfs(int v) {
if(d[v] < 0) return;
for(int to:g[v]) {
dfs(to);
if((int)st[to].size() > (int)st[v].size()) {
st[to].swap(st[v]);
}
for(auto i:st[to]) {
st[v].insert(i);
}
}
ll val = x[v], mn = min(0ll, val);
while(val < 0) {
auto [r, y] = (*st[v].begin());
st[v].erase(st[v].begin());
mn = min(mn, val + r);
val += y;
}
while(!st[v].empty() && (*st[v].rbegin()).first >= mn) {
auto [r, y] = (*st[v].rbegin());
st[v].erase(st[v].find(*st[v].rbegin()));
val += y;
}
st[v].insert({mn, val});
}
void test() {
cin >> n >> s;
for(int i = 1; i <= n; i++) {
cin >> x[i] >> p[i];
g[p[i]].push_back(i);
}
prec(0);
dfs(0);
ll en = s, mx = s;
vector<pair<ll, ll>> vec;
for(auto [y, x]:st[0]) {
vec.push_back({y, x});
}
reverse(vec.begin(), vec.end());
for(auto [y, x]:vec) {
if(en + y < 0) {
break;
}
en += x;
}
cout << en - s << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
test();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 11
Accepted
Test #1:
score: 11
Accepted
time: 176ms
memory: 243076kb
input:
299955 1000000000000000000 -2 0 10 1 -9 2 14 3 -11 4 17 5 -21 6 22 7 -22 8 23 9 -41 10 -89 10 49 11 99 12 -120 14 -23 8 130 15 24 16 -51 13 55 19 -144 20 -24 18 -30 18 -54 13 64 24 -105 14 145 21 -60 20 -183 25 61 28 -334 30 340 31 111 26 -135 33 -184 33 191 35 -231 17 -505 27 -570 32 -257 25 238 37...
output:
551168
result:
ok single line: '551168'
Test #2:
score: 11
Accepted
time: 187ms
memory: 246840kb
input:
299932 1000000000000000000 -26 0 -38 0 -521 0 -567 0 -569 0 -235 0 -294 0 -134 0 144 8 -177 0 -458 0 -9675 9 296 7 -15 0 34 1 -21349 9 -15643 9 -280 0 -445 15 -13253 13 -7497 15 -12328 15 -3131 15 7498 21 -172566 24 -14287 13 -24726 13 -1 0 -12603 13 -14221 13 -401 0 -4105 13 -2872 15 -1264 9 -5095 ...
output:
797403
result:
ok single line: '797403'
Test #3:
score: 11
Accepted
time: 239ms
memory: 254540kb
input:
299978 1000000000000000000 -319087 0 -397343 0 -746276 0 -123466 0 -27323 0 -462189 0 -44293 0 -157047 0 -492663 0 -471747 0 -214986 0 -276045 0 -134544 0 -245003 0 -564286 0 -100579 0 -128044 0 -725767 0 -317957 0 -515861 0 -209544 0 -152961 0 -275236 0 -499829 0 -609630 0 -439399 0 -61718 0 -80829...
output:
822051
result:
ok single line: '822051'
Test #4:
score: 11
Accepted
time: 112ms
memory: 259216kb
input:
295612 1000000000000000000 -59435628 0 -94130 0 98375 2 -101252 3 -376825783 3 376834010 5 59435737 1 110079 4 -107471 8 -142894643 8 123353 9 -125578 11 -205705873 11 142895079 10 205719702 13 128238 12 -563917506 16 563929915 17 -129566 16 139278 19 -134538 20 -146413129 20 145442 21 -150271 23 15...
output:
963990158
result:
ok single line: '963990158'
Test #5:
score: 11
Accepted
time: 91ms
memory: 267672kb
input:
294609 1000000000000000000 -14859 0 -6241 0 28010 1 -35056 3 -18753 3 29895 5 37233 4 -45266 7 15101 2 46739 8 -42054 7 -47262 10 -47937 10 44830 11 59665 13 48681 12 -49712 15 53835 17 -61975 15 67471 19 -66656 20 -73226 20 78369 21 80156 22 -92090 24 97049 25 -95094 26 -85272 24 100554 27 89857 28...
output:
931886923
result:
ok single line: '931886923'
Test #6:
score: 11
Accepted
time: 117ms
memory: 238532kb
input:
189644 1000000000000000000 -98837 0 119840 1 -99489 2 -76401 0 128492 3 116250 4 -96744 6 -99996 5 133521 8 -99952 5 135918 10 -99998 9 -99991 11 112238 12 -585552 14 -123819 14 601536 15 165067 16 143777 13 -1401938 18 114098 7 -99847 21 -846458 17 -552575 18 141499 22 589263 24 -99993 25 -152653 1...
output:
552691392
result:
ok single line: '552691392'
Test #7:
score: 11
Accepted
time: 199ms
memory: 247700kb
input:
299926 1000000000000000000 -57 0 -15 0 -46 0 -55 0 48 3 -169 5 -8 0 177 6 -4865 8 -4422 8 -1012 8 -1923 8 -2220 8 -2564 8 -8023 8 -11744 8 -9739 8 -3532 8 59 4 -7231 8 -427 19 -3318 19 1930 12 -1325 19 -1522 19 -39876 23 -1074 8 -3767 19 3327 22 8024 15 -1385 8 -3305 19 -162944 29 -83345 29 -62607 2...
output:
794592
result:
ok single line: '794592'
Test #8:
score: 11
Accepted
time: 223ms
memory: 255992kb
input:
299977 1000000000000000000 -84323754 0 -757801297 0 -933618002 0 -354897565 0 -199261474 0 -299459024 0 -206406371 0 -36684345 0 -168861756 0 -578610640 0 -268385541 0 -351312602 0 -97363859 0 -196857332 0 -322636524 0 -95194265 0 -680308843 0 -263260235 0 -216910835 0 -226788267 0 -233048009 0 -814...
output:
986969150
result:
ok single line: '986969150'
Test #9:
score: 11
Accepted
time: 99ms
memory: 265616kb
input:
283319 1000000000000000000 -573197 0 573199 1 -39356 0 39360 3 -282938 4 282944 5 -80826 4 80835 7 -85277 8 -311032 8 85286 9 -91485 11 311035 10 -726938 11 91495 12 -120788 15 -98729 15 98735 17 -99389 18 99396 19 120793 16 726946 14 -741076 20 -99753 20 99761 24 741077 23 -99764 25 99765 27 -29131...
output:
660263
result:
ok single line: '660263'
Test #10:
score: 11
Accepted
time: 88ms
memory: 268820kb
input:
299669 1000000000000000000 -4 0 12 1 -5 0 14 3 -10 4 14 5 -19 6 -24 6 27 7 -6 4 11 10 26 8 -31 12 -28 12 40 13 36 14 -33 15 40 17 -32 15 -46 18 37 19 -39 18 52 20 -50 23 46 22 57 24 -48 23 57 27 -52 26 56 29 -54 26 57 31 -55 32 58 33 -59 32 61 35 -60 36 -66 36 67 37 76 38 -125 40 134 41 -127 42 -132...
output:
793816
result:
ok single line: '793816'
Test #11:
score: 11
Accepted
time: 200ms
memory: 246324kb
input:
299996 1000000000000000000 -12777 0 -184 0 -8243 0 22287 1 15966 3 -29966 5 -115395 4 -25952 4 -35816 4 118906 7 -302894 10 -250742 10 -83569 5 26201 8 44836 9 -112875 15 -236247 14 -154710 14 165906 18 -114324 15 118743 20 -2025587 19 -248790 19 -33062 5 -3472669 21 114363 16 -256645 19 -507672 26 ...
output:
986246181
result:
ok single line: '986246181'
Test #12:
score: 11
Accepted
time: 180ms
memory: 242364kb
input:
249970 1000000000000000000 -36928 0 48799 1 -82473 2 -41129 2 -19478 0 47428 4 32207 5 -120777 7 -252259 6 -96443 2 104504 10 -35270 7 -129100 11 -23517 7 -14394 0 142053 13 26675 14 19207 15 -62133 18 -182436 17 -370084 16 188317 20 -285963 6 -63379 17 62790 19 -15725 18 19585 26 -135446 27 -167110...
output:
790209900
result:
ok single line: '790209900'
Test #13:
score: 11
Accepted
time: 139ms
memory: 243744kb
input:
299996 1000000000000000000 -24857 0 -4919 0 34879 1 -38885 0 8630 2 -65139 3 72225 6 -19591 5 -17376 5 20527 9 -85966 7 -191052 7 25119 8 -83197 10 -50123 10 55745 4 -336750 3 -311589 5 208267 12 -2731640 19 -109591 16 86325 11 -2777378 22 84779 14 -350471 13 -71154 16 -1510191 24 -1732689 24 174340...
output:
742832227
result:
ok single line: '742832227'
Subtask #2:
score: 0
Wrong Answer
Test #14:
score: 0
Wrong Answer
time: 31ms
memory: 227324kb
input:
17 5 -3 0 4 1 -4 2 9 3 -5 4 13 5 -6 6 8 7 -23 8 28 9 -26 10 31 11 -28 12 33 13 -39 14 41 15 -7 16
output:
0
result:
wrong answer 1st lines differ - expected: '16', found: '0'
Subtask #3:
score: 0
Wrong Answer
Test #42:
score: 0
Wrong Answer
time: 101ms
memory: 243300kb
input:
300000 0 -1677 0 1678 1 -3010 2 3011 3 -8141 4 8142 5 -11233 6 11234 7 -14400 8 14401 9 -17045 10 17046 11 -19521 12 19522 13 -23178 14 23179 15 -26907 16 26908 17 -28884 18 28885 19 -30742 20 30743 21 -35957 22 35958 23 -38436 24 38437 25 -39739 26 39740 27 -42432 28 42433 29 -47866 30 47867 31 -48...
output:
1
result:
wrong answer 1st lines differ - expected: '150000', found: '1'
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%