QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#440581 | #8342. 生成树 | A_zjzj | 100 ✓ | 66ms | 9300kb | C++17 | 1.8kb | 2024-06-13 20:54:47 | 2024-06-13 20:54:48 |
Judging History
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'