QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#440496 | #8342. 生成树 | A_zjzj | 19 | 56ms | 9296kb | C++17 | 1.7kb | 2024-06-13 19:40:47 | 2024-06-13 19:40: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];
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%