QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#501000	#9159. 登山	tanxi^#	25	252ms	22376kb	C++14	1.7kb	2024-08-02 10:14:27	2024-08-02 10:14:28

Judging History

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

[2024-08-02 10:14:28]
评测

测评结果：25
用时：252ms
内存：22376kb

查看

[2024-08-02 10:14:27]
提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+9,mod=998244353;
int dep[N],f[N],g[N],L[N],R[N],fa[N],d[N];
int dfn[N],siz[N],cnt,mp[N],mx[N];
int id,T,n,fl;
struct bian
{
	int to,lt;
}b[N<<1];
int head[N],top;
void mkb(int l,int r)
{
	b[++top]={r,head[l]};
	head[l]=top;
}
void dfs(int x)
{
	siz[x]=1;
	dfn[x]=++cnt;
	mp[cnt]=x;
	for(int t=head[x];t;t=b[t].lt)
	{
		int y=b[t].to;
		dfs(y);
		siz[x]+=siz[y];
	}
}
void dp(int x)
{
	if(x==1)
	f[x]=1;
	else
	{
		if(fl)
		{
			f[x]=(g[R[x]]-(L[x]?g[L[x]-1]:0)+mod)%mod*siz[x]%mod;
		}
		else
		{
			mx[x]=d[x];
			int mmx=min(R[x],d[x]);
			f[x]=mmx>=L[x]?(g[mmx]-(L[x]?g[L[x]-1]:0)+mod)%mod:0;
			for(int i=dfn[x]+1;i<dfn[x]+siz[x];i++)
			{
				mx[mp[i]]=min(d[mp[i]],mx[fa[mp[i]]]);
				int mmx=min(R[mp[i]],mx[mp[i]]);
				f[x]=(f[x]+(mmx>=L[mp[i]]?(g[mmx]-(L[mp[i]]?g[L[mp[i]]-1]:0)+mod)%mod:0))%mod;
			}
		}
	}
	g[dep[x]]=f[x];
	if(dep[x])
	g[dep[x]]=(g[dep[x]-1]+g[dep[x]])%mod;
	for(int t=head[x];t;t=b[t].lt)
	{
		int y=b[t].to;
		dp(y);
	}
}
signed main()
{
	// freopen("ex_1.in","r",stdin);
	// freopen("mountain.out","w",stdout);
	cin>>id>>T;
	if(id<=5||id==6||id==7||id==10||id==11||id==12)
	{
		if(id>5)
		fl=1;
		while(T--)
		{
			cnt=0;
			memset(head,0,sizeof(head));
			top=0;
			cin>>n;
			memset(f,0,sizeof(f));
			for(int i=2;i<=n;i++)
			{
				cin>>fa[i];
				mkb(fa[i],i);
				dep[i]=dep[fa[i]]+1;
				int l,r;
				cin>>l>>r;
				L[i]=dep[i]-r;
				R[i]=dep[i]-l;
				cin>>d[i];
				d[i]=dep[i]-d[i]-1;
			}
			dfs(1);
			dp(1);
			for(int i=2;i<=n;i++)
			cout<<f[i]<<' ';
			cout<<'\n';
		}
		return 0;
	}
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Pretests

Pretest #1:

score: 5

Accepted

time: 0ms

memory: 12572kb

input:

output:

result:

ok 20 numbers

Pretest #2:

score: 5

Accepted

time: 4ms

memory: 15124kb

input:

output:

19 18 35 1 38 15 50 0 0 15 349 261 0 525 195 0 108 490 0 0 103 632 393 0 814 0 378 625 174 1025 6236 3125 139 2003 1218 1935 37 265 1218 3929 19 0 211 0 19 1135 35695 14466 46868 29814 18352 5053 11375 28739 0 27114 13392 7593 423 2714 22394 22394 15506 1218 8147 13088 0 17493 42846 178996 171635 9 ...

result:

ok 1196 numbers

Pretest #3:

score: 5

Accepted

time: 3ms

memory: 12676kb

input:

output:

20 18 40 1 233 80 39 212 229 41 190 5094 56 0 4147 713 118 0 4129 5124 0 3313 2850 947 21534 9179 903 21496 2811 1 0 0 2811 143571 56660 67998 10105 25021 67687 3214 0 0 82668 44365 27652 38 25699 379349 23912 1787 84893 13400 25076 13513 0 3370 24657 0 24275 58446 49516 740 0 1198 48652 0 942 256 1...

result:

ok 1196 numbers

Pretest #4:

score: 5

Accepted

time: 71ms

memory: 12884kb

input:

output:

1 1 28 83 25 29 108 111 1 79 21 0 29 21 133 133 533 381 1227 345 0 1112 352 21 423 108 236 20 3618 384 2884 2568 2114 0 7325 1427 7325 3531 1211 1211 19325 28 27101 28 25566 28 18010 0 4297 10182 0 104310 18494 85683 1003 13578 130166 229 28179 27681 117683 173543 113521 3918 9870 4030 1902 0 0 2142...

result:

ok 19996 numbers

Pretest #5:

score: 5

Accepted

time: 78ms

memory: 12744kb

input:

output:

2 35 2 3 34 5 34 3 35 277 514 1 0 444 1451 380 134 1106 1071 134 726 0 134 345 64 0 2177 232 69 0 29 1472 1695 0 1625 0 0 1589 0 4219 2460 104 68 725 1235 1337 15332 1171 0 16744 9322 1360 13966 22157 3645 2319 16617 4491 15278 7736 1339 7806 9758 10865 1339 28395 22817 4866 1338 36 4422 64 5226 325...

result:

ok 19996 numbers

Pretest #6:

score: 0

Wrong Answer

time: 242ms

memory: 22280kb

input:

6
4
100000
1 1 1 0
2 1 1 0
3 1 1 0
4 2 2 0
5 1 1 0
6 2 2 0
7 6 6 0
8 3 3 0
9 6 6 0
10 8 8 0
11 6 6 0
12 12 12 0
13 11 11 0
14 2 2 0
15 2 2 0
16 2 2 0
17 9 9 0
18 1 1 0
19 4 4 0
20 18 18 0
21 13 13 0
22 20 20 0
23 3 3 0
24 21 21 0
25 8 8 0
26 11 11 0
27 11 11 0
28 3 3 0
29 21 21 0
30 1 1 0
31 27 27 0...

output:

99999 17256472 629188600 611932128 769033519 157101391 16756477 440631552 843443481 508393296 130019701 99988 456623880 14956638 833157345 54452998 146432667 379230896 406230007 335828576 380395165 301315632 182973950 389813658 352446580 563594710 403112145 756812272 848320161 717486055 830707839 70...

result:

wrong answer 1st numbers differ - expected: '7', found: '99999'

Pretest #7:

score: 0

Wrong Answer

time: 241ms

memory: 19300kb

input:

output:

1 5 1 5 99992 15 15 499960 99992 14956614 399968 5 299976 960558051 299976 2 1199904 199984 609017521 499960 99975 2 960558051 299976 13756710 828808210 960558051 1 1 13656718 14956614 634754473 7 634754473 271264593 99960 14956614 27513420 1 27513420 10357645 772126541 428203839 439581378 14956614 ...

result:

wrong answer 2nd numbers differ - expected: '1', found: '5'

Pretest #8:

score: 0

Wrong Answer

time: 1ms

memory: 5656kb

input:

8
4
100000
1 1 1 0
2 2 2 0
3 3 3 0
4 4 4 2
5 2 2 1
6 6 6 0
7 2 2 0
8 7 7 3
9 4 4 3
10 1 1 4
11 3 3 0
12 8 8 11
13 13 13 7
14 5 5 10
15 8 8 11
16 14 14 5
17 9 9 2
18 17 17 7
19 3 3 1
20 1 1 9
21 14 14 5
22 5 5 17
23 8 8 14
24 8 8 9
25 24 24 7
26 24 24 7
27 17 17 8
28 27 27 27
29 26 26 6
30 17 17 14
3...

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #9:

score: 0

Wrong Answer

time: 1ms

memory: 5728kb

input:

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #10:

score: 0

Wrong Answer

time: 248ms

memory: 22376kb

input:

output:

99999 99998 99997 16956478 50569440 78497288 10871373 974802767 582313009 538460962 628542991 38500215 943710298 722189889 567470325 27689563 425998610 15656488 794328141 51602878 72764311 592700573 318470792 565623815 219733201 498336655 168631392 917765419 945495513 219051459 855965601 56283786 83...

result:

wrong answer 1st numbers differ - expected: '27', found: '99999'

Pretest #11:

score: 0

Wrong Answer

time: 234ms

memory: 18672kb

input:

output:

99995 1 99996 3 16456498 394697786 8 378041303 199990 12 560384847 49669482 16556494 789195587 295358822 838965065 948152696 16556493 4096616 754485739 203355361 488261215 276880292 543840111 199990 420467330 593817309 789295582 24123755 511284049 99969 158688516 378041303 189545578 362866896 536844...

result:

wrong answer 1st numbers differ - expected: '41', found: '99995'

Pretest #12:

score: 0

Wrong Answer

time: 243ms

memory: 19084kb

input:

12
4
100000
1 1 1 0
1 1 1 0
3 1 2 0
3 1 2 0
4 1 1 0
4 1 3 0
6 2 4 0
7 2 4 0
9 1 4 0
8 1 3 0
11 3 3 0
11 5 6 0
12 1 2 0
14 3 3 0
13 2 7 0
16 2 3 0
17 2 4 0
17 7 9 0
17 3 8 0
20 2 6 0
21 10 11 0
21 6 11 0
21 7 9 0
23 3 4 0
24 5 11 0
26 6 9 0
26 5 7 0
27 12 13 0
29 10 10 0
28 1 3 0
31 13 15 0
32 7 13 0...

output:

1 99998 17056474 99999 509593284 51469419 509093289 34312946 102938837 88623192 530535499 16056484 240073029 88623192 490061099 698928332 594740775 17156473 151480758 178707459 99999 252443770 561885829 850409090 321582188 316769133 518404072 34312944 88623192 629775307 131650883 49412359 74997388 5...

result:

wrong answer 2nd numbers differ - expected: '44', found: '99998'

Pretest #13:

score: 0

Wrong Answer

time: 0ms

memory: 5580kb

input:

13
4
100000
1 1 1 0
2 1 2 0
3 2 2 2
4 2 4 1
5 1 2 4
6 4 6 2
7 1 6 4
8 6 6 5
9 5 8 8
10 6 6 1
11 8 11 5
12 8 11 1
13 4 8 6
14 4 7 1
15 11 15 5
16 1 1 10
17 6 9 7
18 8 16 2
19 2 9 10
20 6 20 7
21 12 14 11
22 9 14 14
23 6 7 22
24 12 14 11
25 20 20 21
26 10 20 0
27 19 26 8
28 21 23 12
29 4 13 23
30 15 2...

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #14:

score: 0

Wrong Answer

time: 1ms

memory: 5660kb

input:

14
4
100000
1 1 1 0
2 1 1 1
1 1 1 0
2 1 2 1
4 2 2 1
5 2 2 1
7 1 4 1
8 2 5 3
8 5 5 3
10 2 3 5
11 1 6 5
10 1 4 5
12 5 8 1
12 3 6 5
13 3 6 2
15 2 5 8
17 6 7 6
18 6 8 5
17 10 10 1
18 4 5 5
20 4 11 7
22 8 9 4
23 9 13 12
24 9 13 10
24 6 8 7
26 3 13 13
26 11 14 11
28 11 11 2
27 9 16 8
30 6 12 0
31 13 17 16...

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #15:

score: 0

Wrong Answer

time: 0ms

memory: 5588kb

input:

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #16:

score: 0

Wrong Answer

time: 1ms

memory: 5724kb

input:

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #17:

score: 0

Wrong Answer

time: 1ms

memory: 5584kb

input:

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #18:

score: 0

Wrong Answer

time: 1ms

memory: 5652kb

input:

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #19:

score: 0

Wrong Answer

time: 0ms

memory: 5588kb

input:

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #20:

score: 0

Wrong Answer

time: 0ms

memory: 5648kb

input:

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Final Tests

Test #1:

score: 5

Accepted

time: 0ms

memory: 12804kb

input:

output:

result:

ok 20 numbers

Test #2:

score: 5

Accepted

time: 0ms

memory: 15036kb

input:

output:

34 69 3 1 236 34 104 1 173 749 28 443 36 1 69 2124 271 1 2089 35 1 528 2124 2388 7628 444 4976 12140 35 2388 271 0 193 298 1 444 1 388 0 0 22121 5170 2423 89 9981 236 4511 29441 0 0 28 17308 12797 20 290 0 28 66702 24245 47192 29221 238597 12140 15625 92547 8753 45281 107649 11412 4241 91539 477 118...

result:

ok 1196 numbers

Test #3:

score: 5

Accepted

time: 0ms

memory: 14628kb

input:

output:

25 249 447 129 26 274 929 1 16 0 78 1288 26 275 25 52 17 763 1 1951 3700 851 3253 825 2514 1857 3253 0 6382 19019 20093 9716 823 3914 2067 9277 585 8365 79274 36681 2789 274 274 22165 72494 0 53117 0 2789 300999 0 41180 139365 6759 0 6759 1288 46560 278623 56757 709247 195711 80845 3914 37444 36895 ...

result:

ok 1196 numbers

Test #4:

score: 5

Accepted

time: 65ms

memory: 15016kb

input:

output:

3 2 1 2 41 1 40 3 118 117 207 34 42 81 166 332 33 33 2 41 82 33 3462 235 42 3244 221 0 0 2957 121 99 6338 2342 40 1974 6298 375 11832 39000 0 18301 22749 1315 5762 0 14123 4460 5795 548 0 0 5520 548 33 548 106 9048 0 40 158 0 5137 5137 0 14387 0 30149 9193 2957 160 375 2 82113 375 384 14939 7233 711...

result:

ok 19996 numbers

Test #5:

score: 5

Accepted

time: 63ms

memory: 13252kb

input:

output:

34 33 0 6 65 0 5 1 4 32 14 7 7 0 265 0 264 97 18 229 95 35 223 362 1 1017 1 26 5427 3593 823 2835 878 132 2209 1314 588 24 1550 429 24 7761 264 0 24 1068 837 0 495 1018 8258 430 194 229 34 7967 324 21377 229 14847 1266 0 583 5055 547 0 45349 4362 6902 90 693 16835 10064 693 54761 4611 37001 10523 58...

result:

ok 19996 numbers

Test #6:

score: 0

Wrong Answer

time: 252ms

memory: 22348kb

input:

output:

99999 99998 17156473 16956478 16856480 560562708 16756477 476680296 476280304 89674349 409354419 120115260 392397896 179441871 904069954 868517948 99983 725120619 306715524 63350995 241789649 240689576 759619845 15056494 355197471 389718349 171063700 124494310 99971 751483234 420705241 881548301 999...

result:

wrong answer 1st numbers differ - expected: '13', found: '99999'

Test #7:

score: 0

Wrong Answer

time: 243ms

memory: 18620kb

input:

7
4
100000
1 1 1 0
1 1 1 0
1 1 1 0
1 1 1 0
5 2 2 0
5 2 2 0
7 1 1 0
8 1 1 0
6 1 1 0
7 3 3 0
9 3 3 0
12 2 2 0
10 2 2 0
13 1 1 0
13 4 4 0
13 7 7 0
15 1 1 0
15 7 7 0
16 7 7 0
19 1 1 0
18 8 8 0
19 2 2 0
23 1 1 0
23 5 5 0
24 8 8 0
23 6 6 0
27 3 3 0
28 4 4 0
26 12 12 0
29 6 6 0
30 1 1 0
31 12 12 0
30 9 9 0...

output:

1 1 1 99996 3 99992 15756550 252088916 6 1 15556566 942775195 3 272800954 31513100 1 545601908 15156550 99996 15156550 99996 61566346 307831730 15556566 63026200 902329951 863619999 848463449 3 328289865 3 99992 252088916 13756606 883204338 728995645 260007145 902329951 15156550 752323173 260007145 ...

result:

wrong answer 4th numbers differ - expected: '21', found: '99996'

Test #8:

score: 0

Wrong Answer

time: 1ms

memory: 5636kb

input:

8
4
100000
1 1 1 0
2 2 2 0
3 2 2 1
4 2 2 2
5 3 3 0
6 6 6 2
7 1 1 6
8 8 8 2
9 1 1 6
10 2 2 3
11 4 4 2
12 6 6 5
13 2 2 11
14 1 1 6
15 7 7 4
16 7 7 3
17 14 14 15
18 12 12 12
19 17 17 3
20 20 20 11
21 5 5 7
22 12 12 3
23 14 14 10
24 3 3 1
25 23 23 10
26 5 5 18
27 5 5 25
28 18 18 1
29 2 2 14
30 23 23 3
3...

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #9:

score: 0

Wrong Answer

time: 1ms

memory: 5544kb

input:

9
4
100000
1 1 1 0
1 1 1 0
1 1 1 0
3 1 1 0
4 2 2 1
6 2 2 2
6 1 1 2
8 3 3 2
9 1 1 4
8 4 4 0
9 4 4 0
12 6 6 3
13 3 3 4
13 6 6 3
15 5 5 0
15 2 2 7
15 4 4 2
17 5 5 2
18 5 5 0
18 4 4 6
19 2 2 8
22 8 8 9
23 3 3 10
24 6 6 12
25 7 7 13
24 1 1 11
27 3 3 7
27 12 12 2
28 4 4 0
30 3 3 9
31 15 15 15
32 1 1 7
31 ...

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #10:

score: 0

Wrong Answer

time: 249ms

memory: 22352kb

input:

10
4
100000
1 1 1 0
2 1 1 0
3 3 3 0
4 3 4 0
5 3 5 0
6 1 4 0
7 5 5 0
8 5 7 0
9 3 6 0
10 6 10 0
11 1 2 0
12 8 11 0
13 4 12 0
14 2 12 0
15 7 10 0
16 6 8 0
17 13 15 0
18 8 9 0
19 2 6 0
20 8 14 0
21 3 18 0
22 11 18 0
23 5 11 0
24 6 12 0
25 3 24 0
26 13 23 0
27 3 8 0
28 14 22 0
29 4 26 0
30 1 5 0
31 13 17...

output:

99999 17256472 99997 17156470 611732126 279082508 560162712 576019212 627599917 34598759 33724427 963517246 879142257 215672115 691083805 710899085 774696069 389555460 433534025 633742383 546720793 131875681 389412610 756068338 917596981 198677184 690370145 270770212 845297519 395348729 525262117 43...

result:

wrong answer 1st numbers differ - expected: '16', found: '99999'

Test #11:

score: 0

Wrong Answer

time: 243ms

memory: 19288kb

input:

output:

99999 17356470 17456469 645945080 100000 663401549 593575673 699728222 457651831 404808225 258632870 261645413 454023906 258732870 417868569 828558734 822576795 990335260 15556470 820649641 59821870 15156493 941004622 835369044 472739799 462359460 681237419 626995696 913771527 908047812 388152212 44...

result:

wrong answer 1st numbers differ - expected: '37', found: '99999'

Test #12:

score: 0

Wrong Answer

time: 242ms

memory: 18948kb

input:

output:

99999 17256470 16656470 899491353 99999 17256470 86782345 208277630 208277628 865578402 312416444 17356470 645582034 34012940 16656470 820459475 19621134 783481872 306116451 540782288 253345482 17356470 457350341 138851760 483283191 50913939 272655809 645582034 766825402 609803993 644612632 95181738...

result:

wrong answer 1st numbers differ - expected: '69', found: '99999'

Test #13:

score: 0

Wrong Answer

time: 1ms

memory: 5580kb

input:

13
4
100000
1 1 1 0
2 1 2 1
3 1 2 2
4 1 3 2
5 1 5 4
6 1 4 4
7 6 6 1
8 3 7 5
9 3 4 4
10 5 6 2
11 6 9 4
12 5 11 9
13 1 3 4
14 6 10 10
15 4 6 8
16 3 8 6
17 1 9 3
18 3 13 8
19 3 11 10
20 2 4 11
21 12 13 0
22 13 17 20
23 9 17 1
24 10 11 16
25 22 25 9
26 5 9 4
27 12 27 26
28 13 13 22
29 8 23 1
30 21 23 19...

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #14:

score: 0

Wrong Answer

time: 1ms

memory: 5652kb

input:

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #15:

score: 0

Wrong Answer

time: 1ms

memory: 5540kb

input:

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #16:

score: 0

Wrong Answer

time: 1ms

memory: 5640kb

input:

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #17:

score: 0

Wrong Answer

time: 0ms

memory: 5640kb

input:

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #18:

score: 0

Wrong Answer

time: 1ms

memory: 5712kb

input:

18
4
100000
1 1 1 0
1 1 1 0
3 1 2 1
2 1 2 0
2 2 2 0
5 1 3 1
6 1 1 1
6 2 3 2
6 1 3 2
9 1 4 1
10 2 3 1
12 1 3 0
10 1 4 2
11 2 5 0
12 4 5 1
14 2 4 1
15 5 6 2
16 4 5 5
18 3 3 5
18 1 6 4
18 3 4 4
21 2 4 3
21 4 7 4
23 7 9 3
23 1 5 3
25 3 5 3
26 5 6 2
25 1 7 4
29 3 4 6
30 4 11 2
29 1 3 3
29 1 5 6
32 9 12 0...

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #19:

score: 0

Wrong Answer

time: 1ms

memory: 5668kb

input:

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #20:

score: 0

Wrong Answer

time: 1ms

memory: 5676kb

input:

output:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements