QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#411306 | #8342. 生成树 | feecle6418 | 35 | 55ms | 8164kb | C++17 | 1.6kb | 2024-05-15 11:26:48 | 2024-05-15 11:26:48 |
Judging History
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%