QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#623670 | #8707. Jobs | Dimash# | 11 | 325ms | 310684kb | C++23 | 1.5kb | 2024-10-09 13:39:44 | 2024-10-09 13:39:45 |
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].begin()).first <= mn) {
auto [r, y] = (*st[v].begin());
st[v].erase(st[v].begin());
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;
for(auto [y, x]:st[0]) {
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: 231ms
memory: 290196kb
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: 237ms
memory: 278584kb
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: 199ms
memory: 259896kb
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: 266200kb
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: 108ms
memory: 276956kb
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: 114ms
memory: 247752kb
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: 216ms
memory: 285884kb
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: 207ms
memory: 259308kb
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: 131ms
memory: 273388kb
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: 114ms
memory: 277604kb
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: 325ms
memory: 310684kb
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: 224ms
memory: 293984kb
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: 183ms
memory: 274632kb
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: 14
Accepted
time: 36ms
memory: 225732kb
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:
16
result:
ok single line: '16'
Test #15:
score: 14
Accepted
time: 36ms
memory: 226932kb
input:
17 1 -14 0 21 1 -15 2 16 3 -22 4 29 5 -32 6 34 7 -33 8 35 9 -10 10 -1 0 6 12 -3 13 5 14 -16 15 22 16
output:
7
result:
ok single line: '7'
Test #16:
score: 14
Accepted
time: 28ms
memory: 228052kb
input:
17 4 -4 0 12 1 -5 0 8 3 -13 0 17 5 -38 6 39 7 -3 8 -6 0 12 10 -29 11 35 12 -32 13 39 14 -24 0 31 16
output:
42
result:
ok single line: '42'
Test #17:
score: 14
Accepted
time: 36ms
memory: 225732kb
input:
1998 100000 -119974094 0 120949782 1 -148267915 2 149258545 3 -353200332 4 353781482 5 -409351160 0 410180396 7 -405293412 0 405638769 9 -491561775 0 492142804 11 -38208552 0 38786890 13 -188326000 0 188960234 15 -294174444 16 294530806 17 -430597876 18 431035538 19 -487343715 20 487438668 21 -17231...
output:
33581034
result:
ok single line: '33581034'
Test #18:
score: 0
Wrong Answer
time: 38ms
memory: 226048kb
input:
1996 100000 -59755 0 151138 1 -174993 2 255152 3 -257624 4 322787 5 -293552 6 392535 7 -350940 8 418275 9 -487611 10 515476 11 -507579 12 556319 13 -549422 14 556127 15 -584293 16 638017 17 -613793 18 628801 19 -653479 20 704157 21 -695266 22 732277 23 -727516 24 792824 25 -781086 26 819574 27 -8098...
output:
40521648
result:
wrong answer 1st lines differ - expected: '23781881', found: '40521648'
Subtask #3:
score: 0
Wrong Answer
Test #42:
score: 15
Accepted
time: 162ms
memory: 263340kb
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:
150000
result:
ok single line: '150000'
Test #43:
score: 15
Accepted
time: 144ms
memory: 262016kb
input:
300000 0 -2707 0 2708 1 -35703 2 35704 3 -87028 4 87029 5 -90666 6 90667 7 -144441 8 144442 9 -13210 0 13211 11 -54700 12 54701 13 -65742 14 65743 15 -118284 16 118285 17 -128694 18 128695 19 -7111 0 7112 21 -57902 22 57903 23 -79725 24 79726 25 -110281 26 110282 27 -124571 28 124572 29 -18852 0 188...
output:
150000
result:
ok single line: '150000'
Test #44:
score: 15
Accepted
time: 167ms
memory: 259408kb
input:
300000 0 -62936 0 62937 1 -137762 0 137763 3 -73582 0 73583 5 -66183 0 66184 7 -75047 0 75048 9 -43684 0 43685 11 -2721 0 2722 13 -111595 0 111596 15 -61005 0 61006 17 -85734 0 85735 19 -87099 0 87100 21 -140862 0 140863 23 -12218 0 12219 25 -68482 0 68483 27 -40203 0 40204 29 -34323 0 34324 31 -374...
output:
150000
result:
ok single line: '150000'
Test #45:
score: 15
Accepted
time: 100ms
memory: 282144kb
input:
299994 8 -3 0 11 1 -9 2 15 3 -21 4 25 5 -23 6 33 7 -33 8 40 9 -37 10 44 11 -45 12 48 13 -52 14 60 15 -61 16 65 17 -63 18 66 19 -66 20 69 21 -70 22 75 23 -74 24 77 25 -78 26 88 27 -84 28 92 29 -97 30 106 31 -102 32 104 33 -108 34 112 35 -110 36 116 37 -116 38 121 39 -119 40 127 41 -125 42 131 43 -136...
output:
546593
result:
ok single line: '546593'
Test #46:
score: 0
Wrong Answer
time: 131ms
memory: 280624kb
input:
299982 3 -1 0 4 1 -13 2 18 3 -17 4 22 5 -23 6 32 7 -37 8 39 9 -45 10 53 11 -47 12 49 13 -66 14 69 15 -73 16 81 17 -86 18 94 19 -122 20 126 21 -132 22 140 23 -139 24 145 25 -160 26 169 27 -163 28 167 29 -174 30 184 31 -184 32 190 33 -208 34 212 35 -215 36 216 37 -228 38 234 39 -237 40 243 41 -258 42 ...
output:
817164
result:
wrong answer 1st lines differ - expected: '80601', found: '817164'
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%