QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#419484#8707. Jobspaul200814 252ms47276kbC++141.2kb2024-05-23 23:07:032024-05-23 23:07:04

Judging History

你现在查看的是最新测评结果

  • [2024-05-23 23:07:04]
  • 评测
  • 测评结果:14
  • 用时:252ms
  • 内存:47276kb
  • [2024-05-23 23:07:03]
  • 提交

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);
		swap(s[x],s[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;
}

詳細信息

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 11
Accepted
time: 252ms
memory: 47276kb

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: 0
Time Limit Exceeded

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:


result:


Subtask #2:

score: 14
Accepted

Test #14:

score: 14
Accepted
time: 0ms
memory: 27148kb

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: 8ms
memory: 28088kb

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: 4ms
memory: 27204kb

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: 14ms
memory: 29316kb

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: 4ms
memory: 27700kb

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: 3ms
memory: 28192kb

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: 4ms
memory: 29064kb

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: 7ms
memory: 28720kb

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: 21ms
memory: 27440kb

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: 14ms
memory: 28484kb

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: 4ms
memory: 29168kb

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: 4ms
memory: 28580kb

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: 4ms
memory: 27572kb

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: 28984kb

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: 20ms
memory: 28200kb

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: 12ms
memory: 28112kb

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: 0ms
memory: 29596kb

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: 9ms
memory: 28760kb

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: 6ms
memory: 28352kb

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: 7ms
memory: 28724kb

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: 20ms
memory: 27844kb

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: 17ms
memory: 28876kb

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: 3ms
memory: 27992kb

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: 0ms
memory: 28164kb

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: 3ms
memory: 28340kb

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: 7ms
memory: 28652kb

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: 18ms
memory: 28936kb

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: 4ms
memory: 28208kb

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: 0
Time Limit Exceeded

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:


result:


Subtask #4:

score: 0
Wrong Answer

Dependency #2:

100%
Accepted

Test #76:

score: 29
Accepted
time: 4ms
memory: 28432kb

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: 0ms
memory: 27216kb

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: 3ms
memory: 29132kb

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: 5ms
memory: 29016kb

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: 14ms
memory: 28928kb

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%