QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#419482 | #8707. Jobs | paul2008 | 14 | 845ms | 50448kb | C++14 | 1.2kb | 2024-05-23 23:06:13 | 2024-05-23 23:06:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5;
int p[N], a[N];
vector <int> g[N];
set <pair<int,int> > s[N];
void dfs(int x)
{
for(auto to:g[x])
{
dfs(to);
for(auto p:s[to])
s[x].insert(p);
s[to].clear();
}
if(a[x]>=0)
s[x].insert(make_pair(0,a[x]));
else
{
int now=-a[x], sum=a[x];
while(sum<0 && s[x].size())
{
now = max(s[x].begin()->first-sum,now);
sum += s[x].begin()->second;
s[x].erase(s[x].begin());
}
if(sum<0)
return;
auto ed=s[x].end();
for(auto it=s[x].begin();it!=s[x].end();it++)
if(it->first>now)
{
ed=it;
break;
}
else
sum += it->second;
s[x].erase(s[x].begin(),ed);
if(s[x].size() && s[x].begin()->first<=now)
assert(0);
s[x].insert(make_pair(now,sum));
}
}
signed main()
{
int n,start;
cin >> n >> start;
for(int i=1;i<=n;i++)
{
scanf("%lld %lld",&a[i+1],&p[i+1]);
p[i+1]++;
}
n++;
for(int i=2;i<=n;i++)
g[p[i]].push_back(i);
dfs(1);
int ans=0;
for(auto x:s[1])
if(start>=x.first)
start += x.second, ans += x.second;
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 11
Accepted
time: 845ms
memory: 50448kb
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: 290ms
memory: 46220kb
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: 228ms
memory: 45280kb
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: 0
Time Limit Exceeded
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:
result:
Subtask #2:
score: 14
Accepted
Test #14:
score: 14
Accepted
time: 0ms
memory: 28340kb
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: 4ms
memory: 27532kb
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: 0ms
memory: 27672kb
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: 9ms
memory: 28520kb
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: 14
Accepted
time: 39ms
memory: 27932kb
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:
23781881
result:
ok single line: '23781881'
Test #19:
score: 14
Accepted
time: 23ms
memory: 29260kb
input:
1996 83074 -104912 0 157516 1 -226832 2 244272 3 -236577 4 251249 5 -345494 6 411376 7 -527443 8 582958 9 -583787 10 665523 11 -681920 12 727305 13 -730788 14 757169 15 -844569 16 893388 17 -871493 18 916618 19 -1019572 20 1118628 21 -1135127 22 1163326 23 -1294857 24 1367717 25 -1345986 26 1391230 ...
output:
48888408
result:
ok single line: '48888408'
Test #20:
score: 14
Accepted
time: 11ms
memory: 27292kb
input:
1997 392026 -368613 0 553533 1 -8120957 2 8333895 3 -7985911 4 3312802 5 4435825 6 18517 7 -1014196 8 -10212556 9 11612664 10 -13466519 11 14039962 12 -21043407 13 21174643 14 -21449184 15 22266444 16 -31562006 17 31769754 18 -33458430 19 33563104 20 -34071074 21 34188004 22 -34242437 23 34307017 24...
output:
423307544
result:
ok single line: '423307544'
Test #21:
score: 14
Accepted
time: 6ms
memory: 27912kb
input:
1998 3670 -4263584 0 4318213 1 -4766861 2 4793818 3 -6021755 4 6028915 5 -10981412 6 11043466 7 -14917467 8 14928380 9 -18108504 10 18125244 11 -23575827 12 23586895 13 -24056708 14 24132173 15 -25452036 16 25510395 17 -36702348 18 36770088 19 -37159186 20 37165482 21 -38084372 22 38124010 23 -40075...
output:
30157547
result:
ok single line: '30157547'
Test #22:
score: 14
Accepted
time: 4ms
memory: 28196kb
input:
1996 100000 -47319305 0 47364706 1 -13725945 0 13780218 3 -24704817 4 24745187 5 -44323181 0 44421117 7 -5595173 0 5676261 9 -16802773 10 16822863 11 -8972006 0 8976861 13 -4882300 0 4967180 15 -19353494 16 19362861 17 -7345443 0 7410858 19 -21922402 20 21943524 21 -28082838 22 28092936 23 -41738649...
output:
28784257
result:
ok single line: '28784257'
Test #23:
score: 14
Accepted
time: 4ms
memory: 27352kb
input:
1996 954331 -246525934 0 246824973 1 -171768374 0 171931727 3 -277027442 4 277822284 5 -309469868 6 309597847 7 -285885388 8 -122289714 9 408353344 10 -449147475 11 449304397 12 -99137909 0 99891216 14 -388030661 15 388769528 16 -441565178 17 441709887 18 -53104970 0 53516386 20 -153117624 21 153153...
output:
39368059
result:
ok single line: '39368059'
Test #24:
score: 14
Accepted
time: 46ms
memory: 28612kb
input:
1996 1 -1 0 934596 1 -245994 2 838558 3 -1023435 4 1505077 5 -1253667 6 1510233 7 -1269836 8 1613725 9 -1505401 10 2178612 11 -2036205 12 2410454 13 -4326153 14 4947830 15 -4326154 16 4839162 17 -4352027 18 5026619 19 -4422789 20 4570760 21 -4868075 22 5163827 23 -5607853 24 6199786 25 -6221258 26 6...
output:
3656716
result:
ok single line: '3656716'
Test #25:
score: 14
Accepted
time: 20ms
memory: 29344kb
input:
1997 1 -1 0 4128 1 -3993 2 74560 3 -4107 4 29412 5 -124282 6 167990 7 -266635 8 285731 9 -296541 10 359960 11 -345943 12 403009 13 -559702 14 590908 15 -645298 16 667991 17 -713997 18 770876 19 -724771 20 761259 21 -745145 22 841278 23 -1132098 24 1209778 25 -1149601 26 1169460 27 -1207652 28 124597...
output:
1976688
result:
ok single line: '1976688'
Test #26:
score: 14
Accepted
time: 11ms
memory: 29176kb
input:
1997 221858 -906800 0 1458469 1 -3490423 2 4305248 3 -7528333 4 8000537 5 -7885388 6 7958703 7 -11393926 8 11980747 9 -11747944 10 12721208 11 -17195863 12 17436265 13 -19104428 14 19963703 15 -19221213 16 19790185 17 -26786612 18 27186963 19 -30098944 20 30428098 21 -30159706 22 30725701 23 -345052...
output:
471142643
result:
ok single line: '471142643'
Test #27:
score: 14
Accepted
time: 5ms
memory: 28264kb
input:
1996 849690 -28008524 0 28806149 1 -60092337 2 60377234 3 -86664447 4 86839975 5 -88838841 6 89792065 7 -118219083 8 118579228 9 -130374280 10 130705881 11 -184972834 12 185236973 13 -213002399 14 213944112 15 -225039106 16 225182999 17 -225237975 18 225413754 19 -234633304 20 234637320 21 -25407696...
output:
361576027
result:
ok single line: '361576027'
Test #28:
score: 14
Accepted
time: 10ms
memory: 27948kb
input:
1997 119135 -152044487 0 152804173 1 -397670939 2 397750796 3 -376672967 0 376746022 5 -417762437 6 418515035 7 -34613749 0 34835024 9 -414368835 0 414736822 11 -376229751 0 376495945 13 -384945031 14 385225811 15 -12089459 0 12451971 17 -389844127 18 390409800 19 -273473837 0 274006345 21 -15884699...
output:
27348525
result:
ok single line: '27348525'
Test #29:
score: 14
Accepted
time: 4ms
memory: 27800kb
input:
1998 942452 -17200029 0 17682105 1 -157988703 2 158288198 3 -4465812 0 4520447 5 -83969677 6 84083777 7 -377563619 8 378402838 9 -179102286 0 179287702 11 -182471742 12 182476796 13 -306751887 14 307033334 15 -459185361 16 460089539 17 -264044243 0 264411886 19 -299850633 20 300594894 21 -181708015 ...
output:
451229996
result:
ok single line: '451229996'
Test #30:
score: 14
Accepted
time: 39ms
memory: 28220kb
input:
1997 111 -71 0 70 1 0 2 0 3 -44 4 -61 5 26570 6 -108 7 19586 8 -109 9 77880 10 -110 11 8653 12 -111 13 84092 14 -39918 15 99150 16 -59706 17 95315 18 -128192 19 215712 20 -130737 21 132166 22 -250104 23 349032 24 -254356 25 304569 26 -273875 27 339811 28 -336187 29 355943 30 -404056 31 495501 32 -38...
output:
7053779
result:
ok single line: '7053779'
Test #31:
score: 14
Accepted
time: 17ms
memory: 28236kb
input:
1998 23414 -21438 0 65346 1 -21835 2 97920 3 -23231 4 61068 5 -173492 6 259764 7 -298330 8 340444 9 -314229 10 392678 11 -337064 12 411806 13 -377880 14 439107 15 -407467 16 481499 17 -473066 18 481956 19 -653829 20 706334 21 -1121383 22 1176305 23 -1143687 24 1168817 25 -1282829 26 1291310 27 -1289...
output:
42402445
result:
ok single line: '42402445'
Test #32:
score: 14
Accepted
time: 7ms
memory: 27580kb
input:
1996 82712 -316962 0 348266 1 -656551 2 664343 3 -1202654 4 1206638 5 -2231912 6 2292459 7 -3208507 8 3265411 9 -3283532 10 3290943 11 -3296785 12 3322367 13 -3355692 14 3432232 15 -3603791 16 3664502 17 -3791800 18 3846615 19 -4202013 20 4282980 21 -4239315 22 4286812 23 -4585108 24 4683584 25 -464...
output:
49210123
result:
ok single line: '49210123'
Test #33:
score: 14
Accepted
time: 4ms
memory: 28232kb
input:
1996 412723 -1285799 0 -2785143 1 -1915618 2 -31151 3 -10385 4 -352 5 -834 6 -271 7 -56 8 2286147 9 -1990814 10 -3346 11 -267118 12 -8046 13 -1982 14 -11516 15 -1886 16 5486951 17 -5461283 18 -14404 19 -8792 20 -2625 21 -1260 22 -50 23 -7 24 -5 25 -4 26 -2 27 -5 28 -1 29 6722984 30 -14074029 31 1421...
output:
274648629
result:
ok single line: '274648629'
Test #34:
score: 14
Accepted
time: 4ms
memory: 27464kb
input:
1996 96055 -163124760 0 163196597 1 -439679475 0 440015968 3 -330108552 0 330659538 5 -133814317 0 134036406 7 -361200860 0 361857023 9 -448386315 10 448562742 11 -305879265 0 306771045 13 -21948420 0 22559969 15 -444868398 0 445604686 17 -79688092 0 80526514 19 -161275407 20 162273868 21 -378895805...
output:
217568388
result:
ok single line: '217568388'
Test #35:
score: 14
Accepted
time: 6ms
memory: 28696kb
input:
1998 53059 -17596215 0 17635693 1 -24626608 2 24636115 3 -42169815 4 42235610 5 -48165922 6 48208633 7 -5034181 0 5043935 9 -44483459 10 44555839 11 -9484773 0 9498470 13 -17554127 14 17624124 15 -18632954 16 18643094 17 -11271715 0 11354481 19 -26953622 20 26963318 21 -27911140 0 28010094 23 -33163...
output:
47280019
result:
ok single line: '47280019'
Test #36:
score: 14
Accepted
time: 38ms
memory: 29436kb
input:
1998 100000 -36651 0 79063 1 -66318 2 116300 3 -94671 4 192399 5 -96166 6 121962 7 -99408 8 192332 9 -99527 10 165939 11 -99979 12 162744 13 -99990 14 178653 15 -99995 16 153909 17 -99997 18 102347 19 -99999 20 118015 21 -100000 22 185649 23 -546732 24 547012 25 -120651 26 -200831 27 276570 28 -2039...
output:
33334487
result:
ok single line: '33334487'
Test #37:
score: 14
Accepted
time: 21ms
memory: 28720kb
input:
1998 2750 -2674 0 939050 1 -2698 2 188682 3 -2750 4 349736 5 -76242 6 769422 7 -196140 8 736133 9 -223700 10 677360 11 -464369 12 1046139 13 -954432 14 1062023 15 -2825470 16 3729410 17 -3055569 18 3526003 19 -5955115 20 6192412 21 -8330959 22 8467897 23 -8435464 24 8650112 25 -8500021 26 8610167 27...
output:
62813522
result:
ok single line: '62813522'
Test #38:
score: 14
Accepted
time: 7ms
memory: 28248kb
input:
1996 9484 -482266 0 571044 1 -644059 2 734857 3 -1903590 4 1913094 5 -1969178 6 2030836 7 -2700941 8 2787436 9 -2758519 10 2857182 11 -2817204 12 2902534 13 -3223663 14 3271392 15 -3228009 16 3290047 17 -3937562 18 4026698 19 -3942339 20 3957812 21 -4035116 22 4101986 23 -4362539 24 4395213 25 -4416...
output:
10779086
result:
ok single line: '10779086'
Test #39:
score: 14
Accepted
time: 6ms
memory: 27672kb
input:
1996 43507 -43499 0 74123 1 -4468514 2 4560077 3 -7686298 4 7774199 5 -10115287 6 10210356 7 -15544964 8 15576507 9 -15914328 10 15990423 11 -16194873 12 16267151 13 -17397927 14 17456031 15 -17668924 16 17741741 17 -19882595 18 19960608 19 -21749798 20 21831533 21 -22366924 22 22432174 23 -26775628...
output:
9707042
result:
ok single line: '9707042'
Test #40:
score: 14
Accepted
time: 0ms
memory: 29236kb
input:
1998 16132 -27815063 0 27845919 1 -16124 0 70139 3 -543295 4 564956 5 -43991673 0 44070836 7 -861535 0 892306 9 -27107826 10 27120048 11 -29224292 12 29297130 13 -27370277 0 27442809 15 -38643375 16 38698533 17 -33817752 0 33905960 19 -1485102 0 1495381 21 -41707228 0 41800507 23 -30740171 0 3077709...
output:
6188757
result:
ok single line: '6188757'
Test #41:
score: 14
Accepted
time: 25ms
memory: 29184kb
input:
1991 35671 -22386 0 40467 1 -193576 2 204855 3 -291681 4 353201 5 -353949 6 362997 7 -367838 8 422419 9 -438001 10 530583 11 -473090 12 556111 13 -557456 14 649915 15 -628847 16 711329 17 -738620 18 792063 19 -834325 20 868739 21 -872848 22 963283 23 -896848 24 969140 25 -1001626 26 1073886 27 -1079...
output:
46098536
result:
ok single line: '46098536'
Subtask #3:
score: 0
Time Limit Exceeded
Test #42:
score: 15
Accepted
time: 404ms
memory: 48316kb
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: 143ms
memory: 47500kb
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: 141ms
memory: 44312kb
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: 0
Time Limit Exceeded
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:
result:
Subtask #4:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #76:
score: 29
Accepted
time: 8ms
memory: 28956kb
input:
6 1 3 0 -3 1 -5 0 2 1 6 3 -4 5
output:
6
result:
ok single line: '6'
Test #77:
score: 29
Accepted
time: 3ms
memory: 28336kb
input:
1992 100000 -123091 0 -30281 0 -21906 2 171526 1 -164573 4 78303 3 -539585 6 170968 5 -178934 6 -508341 8 -475191 8 518159 11 636961 7 -1375943 12 -1134601 13 -310451 4 243776 9 -261962 17 331531 18 1201616 15 -1488800 19 519773 10 -1589229 12 -1624437 22 1636816 23 -604851 13 -2491287 20 338512 16 ...
output:
29871319
result:
ok single line: '29871319'
Test #78:
score: 29
Accepted
time: 0ms
memory: 27828kb
input:
1995 100000 -100015 0 -100035 0 -100004 0 -100023 0 100023 1 -100324 5 -100105 5 -43606 0 100107 7 100013 3 -100079 10 100031 4 -100207 12 -100219 10 -102221 9 100224 14 -100359 5 -100113 10 -100242 10 -101073 16 100038 2 -101171 9 -100687 21 -100054 21 -100779 16 101080 20 -100081 5 100365 17 -1004...
output:
2706
result:
ok single line: '2706'
Test #79:
score: 29
Accepted
time: 4ms
memory: 28772kb
input:
1995 100000 -100874 0 -100123 0 -100279 0 -100025 0 -100033 0 -100128 0 -100352 0 100030 4 -100054 0 -100789 0 -100164 0 -100023 0 -100082 0 -100088 0 -100414 0 100883 1 -100106 0 -100132 0 -100210 0 -104174 16 -100573 0 -100043 0 -103937 8 -100089 0 100091 14 100039 5 -100198 0 -100039 0 100046 28 ...
output:
241
result:
ok single line: '241'
Test #80:
score: 0
Wrong Answer
time: 4ms
memory: 27332kb
input:
1991 7 -1255 0 -2528 0 -822 0 -388 0 -1441 0 -2254 0 -3839 0 -782 0 -2530 0 -1586 0 -844 0 -2370 0 -756 0 -1171 0 -3768 0 -1563 0 -2452 0 -1475 0 -4270 0 -2079 0 -599 0 -2220 0 -2065 0 -139 0 1596 10 -1211 0 -4231 0 -3256 0 -348 0 -2600 0 -2036 0 -2011 0 -3473 0 -2426 0 -614 0 -1640 0 -2614 0 -1797 ...
output:
3509
result:
wrong answer 1st lines differ - expected: '4143', found: '3509'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%