QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#440581#8342. 生成树A_zjzj100 ✓66ms9300kbC++171.8kb2024-06-13 20:54:472024-06-13 20:54:48

Judging History

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

  • [2024-06-13 20:54:48]
  • 评测
  • 测评结果:100
  • 用时:66ms
  • 内存:9300kb
  • [2024-06-13 20:54:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned ll;
const int N=1e5+10;
int n,m,d,k,a[N];
tuple<int,int,int>e1[N],e2[N];
struct graph{
	int w,id;
}b[N];
int pos[N],val[N],fa[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
ll suf[N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		e1[i]={w,++u,++v};
	}
	scanf("%d",&d);
	for(int i=1;i<=d;i++){
		scanf("%d%d",&val[i],&b[i].w);
		b[i].id=i;
	}
	scanf("%d",&k);
	for(int x;k--;){
		scanf("%d",&x),a[++x]=1;
	}
	iota(fa,fa+1+n,0);
	sort(e1+1,e1+1+m);
	ll ans=k=0,sum=0;
	for(int i=1;i<=d;i++)sum+=b[i].w;
	for(int i=1;i<=m;i++){
		auto [w,u,v]=e1[i];
		int x=find(u),y=find(v);
		if(x==y)continue;
		if(a[x]>a[y])swap(x,y);
		if(a[x]&&a[y])e1[++k]={w,x,y};
		ans+=1ll*d*w+sum;
		fa[x]=y;
	}
	sort(b+1,b+1+d,[&](graph a,graph b){
		return a.w<b.w;
	});
	for(int i=1;i<=d;i++)pos[b[i].id]=i;
	for(int i=1;i<=d;i++){
		int u=pos[i],v=pos[i%d+1];
		e2[i]={val[i],u,v};
	}
	sort(e2+1,e2+1+d);
	for(int i=k;i>=1;i--){
		suf[i]=suf[i+1]+get<0>(e1[i]);
	}
	// debug(ans);
	// debug(ary(e1,1,k));
	iota(fa,fa+1+d,0);
	for(int i=1;i<d;i++){
		auto [w,x,y]=e2[i];
		if(b[find(x)].w>b[find(y)].w)swap(x,y);
		int l=0,r=k+1,mid;
		for(;l+1<r;){
			mid=(l+r)>>1;
			if(get<0>(e1[mid])+b[find(y)].w<w)l=mid;
			else r=mid;
		}
		ans+=1ll*(k-l+1)*w;
		ans-=suf[r];
		ans-=1ll*(k-l)*b[find(y)].w;
		// debug(w,x,y,b[find(x)].w,b[find(y)].w,i,ans);
		// debug("debug",l,k);
		fa[find(y)]=find(x);
	}
	cout<<ans<<endl;
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif

詳細信息

Subtask #1:

score: 12
Accepted

Test #1:

score: 12
Accepted
time: 1ms
memory: 5860kb

input:

944 1000
0 1 19979907
0 2 90159521
2 3 32007174
2 4 10695503
0 5 59777511
3 6 73026492
6 7 11496766
0 8 47918279
8 9 8272189
7 10 28259306
6 11 59064669
0 12 53523222
5 13 50368482
6 14 20492524
10 15 39588596
13 16 52921781
0 17 8584190
3 18 75211814
0 19 42562331
3 20 91947648
19 21 76707838
20 22...

output:

64775537220711

result:

ok single line: '64775537220711'

Test #2:

score: 12
Accepted
time: 1ms
memory: 3780kb

input:

934 1000
0 1 91017544
1 2 53420157
1 3 41851885
3 4 76007443
3 5 93559125
1 6 18623764
6 7 37343737
7 8 82933871
3 9 7467816
9 10 696739
4 11 23976533
4 12 1268155
3 13 25836854
7 14 82681098
7 15 45501961
5 16 92799450
5 17 37658340
8 18 65560332
6 19 69422753
0 20 33309396
5 21 93074232
3 22 56435...

output:

63564948464200

result:

ok single line: '63564948464200'

Test #3:

score: 12
Accepted
time: 1ms
memory: 3760kb

input:

974 1000
0 1 2133551
1 2 49400886
0 3 46988211
0 4 60793285
2 5 7782393
1 6 21292008
2 7 44719796
3 8 68932222
6 9 60677959
1 10 49260118
6 11 1885866
1 12 77576427
7 13 36100437
9 14 81640510
6 15 73529471
4 16 71864964
16 17 1443381
14 18 52610240
1 19 13778813
19 20 36751849
13 21 4361399
13 22 3...

output:

66447603196816

result:

ok single line: '66447603196816'

Test #4:

score: 12
Accepted
time: 1ms
memory: 3760kb

input:

2 1000
0 1 58143728
1 0 71304983
1 1 66637669
1 1 47275987
0 0 48243757
1 0 52741254
0 1 79615603
0 0 5144972
1 1 73010910
1 0 82609270
1 0 8901386
1 1 65985434
1 0 73079875
1 0 71219260
0 1 43747085
1 1 9824040
0 0 37811743
1 1 68616340
0 1 18119642
1 1 48490257
0 1 68073084
0 1 51336143
1 0 962426...

output:

78944966502

result:

ok single line: '78944966502'

Test #5:

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

input:

767 1000
0 1 64651205
1 2 31677438
1 3 37086466
1 4 43762243
0 5 61571290
1 6 28883164
3 7 58153198
1 8 47473276
6 9 23725042
9 10 12784755
8 11 41753757
5 12 25795568
12 13 14863261
11 14 28265213
0 15 37846661
4 16 84717638
8 17 74715221
2 18 80021825
14 19 97805226
2 20 73855305
7 21 91223757
20 ...

output:

48909152113200

result:

ok single line: '48909152113200'

Subtask #2:

score: 14
Accepted

Test #6:

score: 14
Accepted
time: 54ms
memory: 8476kb

input:

73816 100000
0 1 66516424
1 2 15841637
0 3 96716667
1 4 740781
4 5 98312002
3 6 99173444
0 7 50279616
6 8 8985947
0 9 48215131
5 10 24852085
10 11 35703899
0 12 64791518
12 13 32698481
12 14 73816393
4 15 56900822
8 16 85236492
16 17 90586920
5 18 63100921
5 19 81561043
6 20 93143550
20 21 91319801
...

output:

314656686092559708

result:

ok single line: '314656686092559708'

Test #7:

score: 14
Accepted
time: 56ms
memory: 8172kb

input:

22249 100000
0 1 6884881
1 2 82218799
0 3 72553539
0 4 45806224
2 5 5251571
4 6 57592938
2 7 92654368
7 8 26489992
4 9 83523333
8 10 93614314
0 11 278918
8 12 49916031
4 13 6724864
6 14 94435281
3 15 90745073
9 16 2099333
11 17 30627322
9 18 25724949
1 19 57244329
6 20 4514252
18 21 93015438
4 22 96...

output:

68526518521358078

result:

ok single line: '68526518521358078'

Test #8:

score: 14
Accepted
time: 56ms
memory: 8096kb

input:

15236 100000
0 1 92480516
1 2 24195247
2 3 85702482
2 4 87024363
4 5 30582736
0 6 88465770
6 7 92201935
2 8 96683439
3 9 98306510
5 10 74141115
0 11 16544104
7 12 1628723
4 13 80634505
9 14 47255821
3 15 71225539
12 16 81406322
15 17 34661945
2 18 53209673
10 19 80280007
8 20 78309871
14 21 74006466...

output:

43877976132617649

result:

ok single line: '43877976132617649'

Test #9:

score: 14
Accepted
time: 52ms
memory: 8524kb

input:

69974 100000
0 1 30617098
1 2 87329313
0 3 1457994
3 4 99314932
3 5 34393182
1 6 4907296
5 7 70526305
2 8 32479413
8 9 38369560
2 10 95665032
4 11 87141999
11 12 12896514
4 13 19233535
3 14 22449300
12 15 84724764
6 16 19643056
6 17 88388698
12 18 81836580
5 19 81878701
13 20 18121474
15 21 11615090...

output:

289523251671305574

result:

ok single line: '289523251671305574'

Test #10:

score: 14
Accepted
time: 61ms
memory: 8708kb

input:

84055 100000
0 1 12239441
0 2 32982711
1 3 72129116
3 4 98439626
1 5 73639238
3 6 21601322
2 7 5451502
0 8 97803753
6 9 18191451
8 10 40075910
10 11 82053106
9 12 32380991
8 13 33966297
11 14 85528203
2 15 68931276
6 16 85979984
8 17 25016663
12 18 47886669
2 19 38355515
3 20 1707609
3 21 19448569
7...

output:

369033770970279437

result:

ok single line: '369033770970279437'

Subtask #3:

score: 19
Accepted

Test #11:

score: 19
Accepted
time: 51ms
memory: 8648kb

input:

76297 100000
0 1 4976175
0 2 2164953
0 3 74152347
2 4 73297533
1 5 82647167
1 6 81085309
5 7 84544019
7 8 39192681
7 9 81220260
2 10 93527125
8 11 64860495
8 12 10295460
5 13 37200835
13 14 79212956
3 15 1747004
9 16 53815527
6 17 26034496
1 18 72421398
0 19 38553026
14 20 40272853
18 21 45209740
14...

output:

258411759464526689

result:

ok single line: '258411759464526689'

Test #12:

score: 19
Accepted
time: 47ms
memory: 8108kb

input:

26208 100000
0 1 20156615
0 2 90377798
1 3 29412439
3 4 1821396
2 5 32647209
5 6 20305218
2 7 83152124
7 8 22779229
6 9 40044962
1 10 76364342
7 11 91432875
2 12 47702048
0 13 42875417
9 14 16753942
7 15 46343169
13 16 56534275
14 17 38920005
15 18 50362533
14 19 74805359
9 20 47776308
16 21 8110817...

output:

37882788166479059

result:

ok single line: '37882788166479059'

Test #13:

score: 19
Accepted
time: 50ms
memory: 8172kb

input:

34813 100000
0 1 38075345
1 2 81639416
2 3 73512344
1 4 7609766
1 5 12680478
2 6 23819164
3 7 44696157
6 8 6386590
6 9 67944203
3 10 90900836
8 11 43250838
5 12 96332288
0 13 99475450
3 14 1642492
12 15 40536154
0 16 1092055
11 17 1613740
13 18 12195390
6 19 40577015
13 20 17219138
16 21 87443067
11...

output:

65444013943387100

result:

ok single line: '65444013943387100'

Test #14:

score: 19
Accepted
time: 51ms
memory: 8712kb

input:

76040 100000
0 1 95151840
1 2 3064200
1 3 22618929
0 4 29244971
2 5 89471632
2 6 69227420
2 7 85263836
7 8 77402067
7 9 64519130
7 10 54381855
10 11 40871520
3 12 26611312
7 13 68866074
2 14 95326830
1 15 49918912
14 16 44084189
5 17 76916100
11 18 17261508
13 19 10283472
12 20 20142838
13 21 570558...

output:

257358650782489731

result:

ok single line: '257358650782489731'

Test #15:

score: 19
Accepted
time: 41ms
memory: 8220kb

input:

11255 100000
0 1 74750618
1 2 25735814
1 3 24313558
1 4 6005386
4 5 12416981
0 6 73525827
3 7 68094889
5 8 61962499
0 9 2130653
8 10 8666414
3 11 20986923
8 12 8221405
6 13 63456091
3 14 72748619
4 15 45148849
8 16 30097917
10 17 6061348
4 18 18187300
14 19 37921044
12 20 23840830
19 21 64103119
14 ...

output:

7409279921740786

result:

ok single line: '7409279921740786'

Subtask #4:

score: 23
Accepted

Test #16:

score: 23
Accepted
time: 65ms
memory: 9300kb

input:

100000 99999
0 1 32047404
1 2 48846560
0 3 20917952
2 4 49845310
0 5 25506424
1 6 55259638
1 7 85124434
1 8 47161335
1 9 82164751
7 10 89665595
6 11 67914199
10 12 60941604
7 13 47472049
8 14 49387818
0 15 56542134
1 16 78765445
5 17 1537626
7 18 10090056
8 19 78639049
19 20 70662646
1 21 91412564
1...

output:

434131763752145809

result:

ok single line: '434131763752145809'

Test #17:

score: 23
Accepted
time: 63ms
memory: 9284kb

input:

100000 99999
0 1 60421577
1 2 40463258
0 3 99799773
0 4 84774638
1 5 76296909
2 6 14452143
6 7 48169195
2 8 28512540
4 9 3491587
3 10 22460289
8 11 47399655
3 12 6894946
7 13 66034146
8 14 76479730
5 15 17440576
6 16 23690934
3 17 49800141
11 18 58002832
10 19 96778193
2 20 83477842
9 21 83311119
20...

output:

435860873420662689

result:

ok single line: '435860873420662689'

Test #18:

score: 23
Accepted
time: 66ms
memory: 9296kb

input:

100000 99999
0 1 56832134
0 2 71090223
0 3 74408869
2 4 97716848
1 5 66916245
4 6 64582656
5 7 64719473
2 8 60209964
1 9 55996184
0 10 27458513
1 11 65806418
10 12 33639905
9 13 82729709
10 14 67571741
5 15 51483621
12 16 12532115
10 17 67142055
2 18 31146510
18 19 7024792
14 20 54238427
17 21 31594...

output:

434070160072307452

result:

ok single line: '434070160072307452'

Test #19:

score: 23
Accepted
time: 54ms
memory: 9296kb

input:

100000 99999
0 1 48062472
0 2 75667062
2 3 29058100
2 4 44533823
3 5 4584876
0 6 51363769
6 7 22200690
0 8 5009671
0 9 89161554
9 10 53540705
2 11 45391393
9 12 55710871
5 13 51373584
8 14 60558032
11 15 57401622
7 16 93143364
14 17 21778320
6 18 33324556
13 19 15246710
16 20 6363423
6 21 78218886
1...

output:

433857853166927215

result:

ok single line: '433857853166927215'

Test #20:

score: 23
Accepted
time: 54ms
memory: 9220kb

input:

100000 99999
0 1 71259344
1 2 9824455
1 3 11617667
3 4 25360309
2 5 63448893
2 6 70516000
2 7 10865547
7 8 70471103
6 9 25750230
1 10 47748234
6 11 41268823
0 12 41558084
11 13 27900200
7 14 83121760
2 15 17756201
14 16 15085617
8 17 38508868
9 18 78714082
13 19 26284893
14 20 46792885
6 21 25181814...

output:

434042863011937996

result:

ok single line: '434042863011937996'

Subtask #5:

score: 32
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #21:

score: 32
Accepted
time: 59ms
memory: 8216kb

input:

17845 100000
0 1 31852299
1 2 27572439
2 3 16658230
3 4 18132105
3 5 20996882
3 6 31924387
3 7 83614799
4 8 60327873
7 9 49525395
4 10 47876417
8 11 71968398
3 12 13768131
9 13 88240375
13 14 78445077
6 15 80773315
14 16 12144674
16 17 90694157
10 18 63804291
0 19 87496918
15 20 953578
4 21 80838320...

output:

83376522408326409

result:

ok single line: '83376522408326409'

Test #22:

score: 32
Accepted
time: 65ms
memory: 8588kb

input:

79143 100000
0 1 78344468
0 2 77546168
2 3 65056497
0 4 56449818
2 5 82834793
1 6 26378770
3 7 73396621
3 8 62522917
7 9 7263259
9 10 21738320
1 11 58785951
9 12 56297094
10 13 71468270
10 14 94487872
6 15 43603133
5 16 919412
12 17 51749740
1 18 98364235
1 19 88160700
5 20 93728415
3 21 95948559
19...

output:

512542501891202626

result:

ok single line: '512542501891202626'

Test #23:

score: 32
Accepted
time: 49ms
memory: 8184kb

input:

22794 100000
0 1 60131904
1 2 76902612
1 3 735416
2 4 97262995
1 5 34713018
5 6 81469310
1 7 90782776
3 8 76076903
7 9 31505900
2 10 34658460
8 11 30810902
10 12 53139871
10 13 53736930
1 14 35052556
4 15 20246261
9 16 62915638
12 17 5071502
14 18 23187614
6 19 63367037
3 20 16692942
15 21 24044318
...

output:

110654272244937365

result:

ok single line: '110654272244937365'

Test #24:

score: 32
Accepted
time: 41ms
memory: 7980kb

input:

461 100000
0 1 28103193
1 2 67058771
1 3 78466037
0 4 74865352
0 5 53178932
5 6 77411475
5 7 63795440
7 8 43311415
2 9 48006477
2 10 3106652
9 11 4085716
1 12 32915160
3 13 28905215
9 14 26221315
5 15 29995095
10 16 69928994
7 17 61253714
14 18 67386492
8 19 74115016
0 20 27129329
0 21 42523776
5 22...

output:

1807187146419332

result:

ok single line: '1807187146419332'

Test #25:

score: 32
Accepted
time: 60ms
memory: 8412kb

input:

44596 100000
0 1 75009442
0 2 12080543
0 3 43382446
3 4 92736849
0 5 93767656
0 6 46885576
3 7 18989997
7 8 43502528
2 9 77209845
6 10 75565393
8 11 44045570
9 12 73202438
4 13 66368907
11 14 53415133
5 15 7803228
5 16 55851582
16 17 44996666
5 18 70772287
1 19 22981972
11 20 93085930
8 21 542983
11...

output:

249866683292547896

result:

ok single line: '249866683292547896'