QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#411306#8342. 生成树feecle641835 55ms8164kbC++171.6kb2024-05-15 11:26:482024-05-15 11:26:48

Judging History

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

  • [2024-05-15 11:26:48]
  • 评测
  • 测评结果:35
  • 用时:55ms
  • 内存:8164kb
  • [2024-05-15 11:26:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pr;
const ll inf=1e9;
struct E{
	int x,y,z;
}e[100005],reale[10005];
int n,m,fa[100005],a[100005],b[100005],L,R,is[100005],A,val[100005],cnt,pl[100005];
ll ans=0,sb=0,sv[100005];
int gf(int x){
	return x==fa[x]?x:fa[x]=gf(fa[x]);
}
int getcomp(int x){
	int pos=upper_bound(val+1,val+R,x)-val-1;
	return R-pos;
}
ll getse(int id,int x){
	int pos=upper_bound(val+1,val+R,x)-val-1;
	return sv[pos]+1ll*pos*b[id];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,z;i<=m;i++)scanf("%d%d%d",&x,&y,&z),e[i]={x+1,y+1,z};
	sort(e+1,e+m+1,[](E x,E y){return x.z<y.z;});
	scanf("%d",&L);
	for(int i=1;i<=L;i++)scanf("%d%d",&a[i],&b[i]),sb+=b[i];
	scanf("%d",&R);
	for(int i=1,x;i<=R;i++)scanf("%d",&x),is[x+1]=1,A=x+1;
	for(int i=1;i<=n;i++)fa[i]=(is[i]?A:i);
	for(int i=1;i<=m;i++){
		int x=gf(e[i].x),y=gf(e[i].y);
		if(x==y)continue;
		fa[x]=y,reale[++cnt]=e[i],ans+=1ll*L*e[i].z+sb;
	}
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=cnt;i++)fa[gf(reale[i].x)]=gf(reale[i].y);
	int ts=0;
	for(int i=1;i<=m;i++){
		int x=gf(e[i].x),y=gf(e[i].y);
		if(x==y)continue;
		fa[x]=y,val[++ts]=e[i].z,sv[ts]=sv[ts-1]+e[i].z;
	}
	assert(ts==R-1);
	for(int i=1;i<=L;i++)fa[i]=i,pl[i]=i;
	sort(pl+1,pl+L+1,[](int x,int y){return a[x]<a[y];});
	for(int i=1;i<L;i++){
		int x=gf(pl[i]),y=gf(x%L+1);
		if(b[x]<b[y]){
			ans+=1ll*a[x]*getcomp(a[x]-b[y])+getse(y,a[x]-b[y]);
			fa[x]=y,b[y]=b[x];
		}
		else {
			ans+=1ll*a[x]*getcomp(a[x]-b[x])+getse(x,a[x]-b[x]);
			fa[x]=y;
		}
	}
	//cout<<a[gf(1)]-b[gf(1)]<<'\n';
	cout<<ans+getse(gf(1),inf);
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 12
Accepted

Test #1:

score: 12
Accepted
time: 2ms
memory: 7792kb

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: 0
Accepted
time: 1ms
memory: 5880kb

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: 0
Accepted
time: 1ms
memory: 7920kb

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: 0
Accepted
time: 0ms
memory: 5900kb

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: 0
Accepted
time: 1ms
memory: 5676kb

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: 0
Runtime Error

Test #6:

score: 0
Runtime Error

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:


result:


Subtask #3:

score: 0
Runtime Error

Test #11:

score: 0
Runtime Error

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:


result:


Subtask #4:

score: 23
Accepted

Test #16:

score: 23
Accepted
time: 55ms
memory: 8164kb

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: 0
Accepted
time: 50ms
memory: 7988kb

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: 0
Accepted
time: 54ms
memory: 8120kb

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: 0
Accepted
time: 54ms
memory: 8128kb

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: 0
Accepted
time: 52ms
memory: 8076kb

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: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%