QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#717914#9580. 插排串联NULL_SFWA 28ms10192kbC++231.1kb2024-11-06 19:15:402024-11-06 19:15:46

Judging History

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

  • [2024-11-06 19:15:46]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:10192kb
  • [2024-11-06 19:15:40]
  • 提交

answer

#include <iostream>
#include <vector>
#include <algorithm>

#define int long long

using namespace std;

vector<int> son[100001];
int w[100001],depth[100001],sum[100001],curr=0;
vector<int> save;

void dfs(int u)
{
	int maxi=0;
	
	for(auto v:son[u])
	{
		dfs(v);
		
		maxi=max(maxi,depth[v]);
	}
	
	depth[u]=maxi+1;
	
	return;
}

void dfs2(int u)
{
	if((int)son[u].size()==0)
	{
		sum[u]=w[++curr];
		
		return;
	}
	
	for(auto v:son[u]){
		dfs2(v);
		
		sum[u]+=sum[v];
	}
	
	save.push_back(sum[u]);
	
	return;
}

bool cmp(int x,int y)
{
	return depth[x]>depth[y];
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	
	int n;
	
	cin>>n;
	for(int i=1;i<=n;i++){
		int fa;
		cin>>fa>>w[i];
		
		son[fa].push_back(i);
	}
	w[++n]=2200;
	
	sort(w+1,w+n+1);
	
	dfs(0);
	
	for(int i=0;i<=n;i++){
		sort(son[i].begin(),son[i].end(),cmp);
	}
	
	dfs2(0);
	
	sort(save.begin(),save.end());
	for(int i=curr+1,j=0;i<=n;i++,j++)
	{
		if(save[j]>w[i])
		{
			cout<<"NO\n";
			return 0;
		}
	}
	
	cout<<"YES\n";
	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5684kb

input:

5
0 500
1 700
1 400
2 100
2 200

output:

YES

result:

ok single line: 'YES'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5680kb

input:

5
0 500
1 700
1 400
2 100
2 300

output:

NO

result:

ok single line: 'NO'

Test #3:

score: 0
Accepted
time: 1ms
memory: 5632kb

input:

4
0 1000
1 800
1 500
2 300

output:

YES

result:

ok single line: 'YES'

Test #4:

score: 0
Accepted
time: 1ms
memory: 5664kb

input:

3
0 1000000000
0 1000000000
0 147483647

output:

NO

result:

ok single line: 'NO'

Test #5:

score: 0
Accepted
time: 0ms
memory: 5628kb

input:

3
0 1000000000
0 1000000000
0 147483648

output:

NO

result:

ok single line: 'NO'

Test #6:

score: 0
Accepted
time: 16ms
memory: 8568kb

input:

64855
0 69748768
0 450926072
1 699448620
3 918617238
4 106189312
1 617660017
5 31691747
2 373080156
0 363984605
0 937885158
10 300431710
8 485372487
1 661592241
1 836709079
13 895424425
1 824052267
9 887752080
15 952380329
0 595041339
14 632034017
18 752444470
4 311747126
2 289503382
11 213029500
23...

output:

NO

result:

ok single line: 'NO'

Test #7:

score: 0
Accepted
time: 12ms
memory: 7868kb

input:

48750
0 3785579
1 2060436
1 1095269
2 3527822
3 2748694
3 452943
5 427867
3 191538
8 2095981
1 3895276
10 3771233
3 3121067
10 416014
9 1443750
1 699351
8 933800
7 361157
16 423718
10 785063
11 2772134
16 3135666
2 1404821
15 417197
12 1560818
4 2709779
13 2489882
24 1070706
23 2364628
22 3451655
8 ...

output:

YES

result:

ok single line: 'YES'

Test #8:

score: 0
Accepted
time: 15ms
memory: 9704kb

input:

84633
0 948740
0 641037
1 718701
2 1491463
4 650546
3 186260
0 1582777
2 3382499
7 422546
7 173919
5 22805
4 2525048
3 55722
13 2477450
4 3136570
0 2480252
8 3021218
5 2229161
6 2865608
19 1079977
17 1435746
4 1313091
12 2415924
23 916623
10 1085785
23 183229
21 2851467
7 3273898
2 1704183
21 108474...

output:

YES

result:

ok single line: 'YES'

Test #9:

score: 0
Accepted
time: 1ms
memory: 5872kb

input:

3085
0 156408
0 605147
0 642324
3 1439620
2 3777153
3 2138026
6 3201634
1 798924
3 3675188
1 738670
10 1065151
4 2642031
3 1039262
4 166483
9 2901954
13 3220176
8 1473831
17 111635
5 1850998
13 2979810
3 2209665
11 1159203
5 1423601
14 1866708
6 190085
20 515853
18 249432
19 3420517
5 880307
16 1633...

output:

YES

result:

ok single line: 'YES'

Test #10:

score: 0
Accepted
time: 8ms
memory: 6896kb

input:

33563
0 3441366
1 127545
1 990142
3 2881275
3 341896
0 1222841
3 3636614
3 1463437
7 1590040
7 1831330
5 718702
10 3734001
8 1638244
12 1896130
10 3378576
5 1467271
5 2093043
15 2417613
14 2357653
9 2048870
1 2888379
10 2675645
8 1497902
2 121692
24 652159
7 3209636
22 3675284
9 1882852
20 2574783
2...

output:

YES

result:

ok single line: 'YES'

Test #11:

score: 0
Accepted
time: 7ms
memory: 6836kb

input:

29579
0 2878456
0 1914553
0 3052352
1 3523343
2 3422684
5 2367471
0 2376896
1 2974820
8 3189629
6 3453774
6 1361998
7 3775154
3 1233399
9 2587463
11 1661485
12 1649552
8 827050
7 1923272
12 2038094
10 3047323
15 3315098
8 1793575
0 1533561
1 3394249
20 409631
2 3082593
2 3216618
17 1508657
0 2224882...

output:

YES

result:

ok single line: 'YES'

Test #12:

score: 0
Accepted
time: 2ms
memory: 5936kb

input:

4257
0 2746453
1 934664
2 1811694
1 1881261
1 828421
2 3823291
4 2495811
5 3492588
8 2811330
4 1868923
9 3158727
0 2588343
0 812790
2 2451335
12 140610
0 2094375
9 1299381
13 3575
16 1013273
9 1885065
6 2846770
4 2248441
22 2918503
0 388423
17 34262
5 1912487
7 3489140
14 1786954
10 468842
10 799647...

output:

YES

result:

ok single line: 'YES'

Test #13:

score: 0
Accepted
time: 0ms
memory: 6120kb

input:

9989
0 37781884
0 106132563
2 234509818
1 39119130
1 713838599
5 889820764
2 38974740
2 359166567
0 67252682
4 376616158
10 625610443
4 919055330
10 5279094
4 235214277
6 583045590
8 799849577
6 879221313
10 638915861
8 856423881
16 791822942
6 91775189
14 414069330
2 702728259
6 782025710
19 456290...

output:

NO

result:

ok single line: 'NO'

Test #14:

score: 0
Accepted
time: 10ms
memory: 7304kb

input:

32007
0 28588942
1 588910732
1 822998678
1 31311276
4 270556381
0 895262877
1 245584694
2 600724483
0 360443315
7 327778173
0 229941301
4 411052996
9 317062555
2 822712314
10 174748461
15 202513163
14 51641000
13 322140013
14 846578787
14 200468205
11 120900618
19 92414230
3 212657879
23 38016953
19...

output:

NO

result:

ok single line: 'NO'

Test #15:

score: 0
Accepted
time: 11ms
memory: 8444kb

input:

62480
0 344484173
1 959220640
1 346311519
3 682971330
0 872962167
5 654054678
1 211950711
3 279636241
1 874351670
2 589327983
2 759732770
4 39012678
1 304520249
13 205761290
9 49505548
2 472723770
8 294877579
8 101446926
0 106436261
9 663722761
12 626129657
7 257345486
19 522538943
17 391435814
22 2...

output:

NO

result:

ok single line: 'NO'

Test #16:

score: 0
Accepted
time: 5ms
memory: 6504kb

input:

15057
0 547431950
1 438631643
1 179667650
3 845345949
3 392421818
4 619759838
3 655010794
4 552746270
5 348211967
8 749755552
8 214419083
5 436972181
7 144606612
10 47659129
7 836963756
8 997710335
5 464546999
10 956455992
9 6490937
12 839906551
10 548394757
2 512718784
17 735705457
21 841989848
3 5...

output:

NO

result:

ok single line: 'NO'

Test #17:

score: 0
Accepted
time: 24ms
memory: 9392kb

input:

79665
0 26601262
1 351073371
0 562669496
1 113861629
0 488720325
3 143645132
2 152367902
2 223288443
1 701505717
5 651806214
0 315664642
5 890947643
6 332686746
8 991291180
11 806170547
1 536624
10 580277712
8 851400609
12 831169455
13 426350055
1 96295828
0 40613494
2 138212373
10 711465091
0 53528...

output:

NO

result:

ok single line: 'NO'

Test #18:

score: 0
Accepted
time: 17ms
memory: 7352kb

input:

54465
0 622736731
1 420881358
0 410079334
0 919962271
3 640215698
5 876473905
6 551273644
3 762238835
2 209117994
7 840764274
3 170436503
4 55241632
10 527700919
0 298040566
3 572894095
7 496841254
1 774443487
1 760496188
17 95740952
11 816157971
17 651436270
9 611917010
1 356463954
5 933438
22 2506...

output:

NO

result:

ok single line: 'NO'

Test #19:

score: 0
Accepted
time: 26ms
memory: 9572kb

input:

81711
0 282604662
1 947414489
2 921146841
3 275753907
2 421291646
4 714882857
1 415741693
5 440078624
7 51188033
6 475790320
6 208861039
0 129590461
3 136073895
0 84000148
9 962967221
8 9984299
13 801017811
9 827504075
3 525642572
17 853670683
6 144426274
17 245662201
18 791510290
22 43729178
21 382...

output:

NO

result:

ok single line: 'NO'

Test #20:

score: 0
Accepted
time: 27ms
memory: 10192kb

input:

96384
0 638462063
0 932608620
2 106211095
1 411417864
1 102796102
2 308927943
3 274807824
1 881458892
4 590352291
1 942231453
10 790716863
5 74008267
1 529155326
0 670276831
14 776970473
12 521913382
12 154429959
11 351006589
18 801507747
16 799119494
9 178502115
6 712119667
21 610240217
20 86211900...

output:

NO

result:

ok single line: 'NO'

Test #21:

score: 0
Accepted
time: 28ms
memory: 9724kb

input:

88157
0 521696562
1 571911131
1 500294151
3 541557733
2 122797269
5 30062326
3 488414871
0 62695298
2 974096972
4 34910748
3 458253569
0 4448449
9 824555997
5 1137692
0 46166453
10 816075570
5 53938845
0 17831235
15 776612881
19 637474003
10 538818723
7 589940160
9 109597025
8 879598110
10 583872754...

output:

NO

result:

ok single line: 'NO'

Test #22:

score: 0
Accepted
time: 23ms
memory: 9688kb

input:

86463
0 772657728
0 457367394
2 782823785
0 827081806
0 491193885
4 934172213
0 467521287
7 700005049
8 365825625
7 67729553
8 926143356
2 406015284
11 296314083
0 148561677
13 643876057
1 195769150
12 132245858
15 317641983
18 100214983
14 339940318
12 48571712
9 406835152
9 743988693
18 127792964
...

output:

NO

result:

ok single line: 'NO'

Test #23:

score: 0
Accepted
time: 2ms
memory: 5828kb

input:

6153
0 627308529
1 80177490
1 499455943
1 123888319
0 749943105
2 4153132
6 322192789
4 555406930
7 666123545
5 626111562
1 943285967
4 166408480
9 276658989
9 31650069
2 15959645
4 704639761
10 544389564
14 294936722
14 308217464
0 45514459
5 624533570
20 150925578
22 185894976
23 631570196
20 7100...

output:

NO

result:

ok single line: 'NO'

Test #24:

score: 0
Accepted
time: 1ms
memory: 5672kb

input:

1
0 1

output:

YES

result:

ok single line: 'YES'

Test #25:

score: -100
Wrong Answer
time: 0ms
memory: 3572kb

input:

1
0 1000000000

output:

YES

result:

wrong answer 1st lines differ - expected: 'NO', found: 'YES'