QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#440496#8342. 生成树A_zjzj19 56ms9296kbC++171.7kb2024-06-13 19:40:472024-06-13 19:40:48

Judging History

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

  • [2024-06-13 19:40:48]
  • 评测
  • 测评结果:19
  • 用时:56ms
  • 内存:9296kb
  • [2024-06-13 19:40: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];
		if(u>v)swap(u,v);
		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(ary(e1,1,k));
	for(int i=1;i<d;i++){
		auto [w,x,y]=e2[i];
		int l=0,r=k+1,mid;
		for(;l+1<r;){
			mid=(l+r)>>1;
			if(get<0>(e1[mid])+b[y].w<w)l=mid;
			else r=mid;
		}
		ans+=1ll*(k-l+1)*w;
		ans-=suf[r];
		ans-=1ll*(k-l)*b[y].w;
		debug(i,ans);
	}
	cout<<ans<<endl;
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 5772kb

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:

59070483301044

result:

wrong answer 1st lines differ - expected: '64775537220711', found: '59070483301044'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 49ms
memory: 9052kb

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:

253592485973963484

result:

wrong answer 1st lines differ - expected: '314656686092559708', found: '253592485973963484'

Subtask #3:

score: 19
Accepted

Test #11:

score: 19
Accepted
time: 43ms
memory: 8488kb

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

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

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

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

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: 0
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 56ms
memory: 9296kb

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:

315960046095860956

result:

wrong answer 1st lines differ - expected: '434131763752145809', found: '315960046095860956'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%