NOI.AC
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #213149 | #584. t3 | Invisible_H | 0 | 412ms | 4328kb | C++ | 3.7kb | 2024-11-09 21:28:06 | 2024-11-09 23:21:11 |
answer
#include <bits/stdc++.h>
using namespace std;
const long long MX=200100,INF=0x3f3f3f3f;
long long fath[MX];
long long fnd(long long x){
if(x==fath[x]) return x;
return fath[x]=fnd(fath[x]);
}
bool merge(long long x,long long y){
long long fx=fnd(x),fy=fnd(y);
if(fx==fy) return 0;
if(rand()&1) swap(fx,fy);
fath[fx]=fy;
return 1;
}
struct node{
long long x,y,w;
}edge[MX<<1];
inline bool cmp(node a,node b){
return a.w<b.w;
}
signed main(){
long long n,m,k;scanf("%lld%lld%lld",&n,&m,&k);
for(long long i=1;i<=n;i++) fath[i]=i;
for(long long i=1;i<=m;i++){
long long x,y,w;scanf("%lld%lld%lld",&x,&y,&w);
edge[i]={x,y,w};
}
sort(edge+1,edge+1+m,cmp);
long long cnt=0,sum=0,ans=0;
for(long long i=1;i<=m;i++){
if(merge(edge[i].x,edge[i].y)){
// printf("%lld %lld\n",edge[i].x,edge[i].y);
sum++;
cnt=max(cnt,edge[i].w);
if(cnt>k)ans+=cnt-k;
if(sum==n-1) break;
}
}
if(cnt<k){
ans=0x3f3f3f3f;
for(long long i=1;i<=m;i++){
ans=min(ans,abs(k-edge[i].w));
}
}
printf("%lld\n",ans);
return 0;
}
/*
CCCCCCCCCCCCC AAA IIIIIIIIII CCCCCCCCCCCCC AAA IIIIIIIIII AAA
CCC::::::::::::C A:::A I::::::::I CCC::::::::::::C A:::A I::::::::I A:::A
CC:::::::::::::::C A:::::A I::::::::I CC:::::::::::::::C A:::::A I::::::::I A:::::A
C:::::CCCCCCCC::::C A:::::::A II::::::IIC:::::CCCCCCCC::::C A:::::::A II::::::II A:::::::A
C:::::C CCCCCC A:::::::::A I::::I C:::::C CCCCCC A:::::::::A I::::I A:::::::::A
C:::::C A:::::A:::::A I::::IC:::::C A:::::A:::::A I::::I A:::::A:::::A
C:::::C A:::::A A:::::A I::::IC:::::C A:::::A A:::::A I::::I A:::::A A:::::A
C:::::C A:::::A A:::::A I::::IC:::::C A:::::A A:::::A I::::I A:::::A A:::::A
C:::::C A:::::A A:::::A I::::IC:::::C A:::::A A:::::A I::::I A:::::A A:::::A
C:::::C A:::::AAAAAAAAA:::::A I::::IC:::::C A:::::AAAAAAAAA:::::A I::::I A:::::AAAAAAAAA:::::A
C:::::C A:::::::::::::::::::::A I::::IC:::::C A:::::::::::::::::::::A I::::I A:::::::::::::::::::::A
C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A I::::I C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A I::::I A:::::AAAAAAAAAAAAA:::::A
C:::::CCCCCCCC::::C A:::::A A:::::A II::::::IIC:::::CCCCCCCC::::C A:::::A A:::::A II::::::II A:::::A A:::::A
CC:::::::::::::::C A:::::A A:::::A I::::::::I CC:::::::::::::::C A:::::A A:::::A I::::::::I A:::::A A:::::A
CCC::::::::::::C A:::::A A:::::A I::::::::I CCC::::::::::::C A:::::A A:::::A I::::::::I A:::::A A:::::A
CCCCCCCCCCCCCAAAAAAA AAAAAAAIIIIIIIIII CCCCCCCCCCCCCAAAAAAA AAAAAAAIIIIIIIIIIAAAAAAA AAAAAAA
*/
Details
小提示：点击横条可展开更详细的信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 1484kb
input:
458 823 14431 9895 11970 15308 2575 20181 709 27999 12992 18884 11061 16281 5044 28990 25092 28337 3...
output:
255625
result:
wrong answer 1st lines differ - expected: '806084096', found: '255625'
Test #2:
score: 0
Wrong Answer
time: 1ms
memory: 1480kb
input:
481 526 8409 14498 18636 10027 24362 32458 17986 17730 11956 19192 2193 1034 29317 19284 16210 26242...
output:
367660
result:
wrong answer 1st lines differ - expected: '867105097', found: '367660'
Test #3:
score: 0
Wrong Answer
time: 43ms
memory: 4324kb
input:
100000 100000 15247 4194 9619 4532 22058 2667 21549 16652 25327 12018 13395 11426 7243 11714 22904 2...
output:
425054942
result:
wrong answer 1st lines differ - expected: '54433', found: '425054942'
Test #4:
score: 0
Wrong Answer
time: 57ms
memory: 4324kb
input:
100000 100000 6264 26207 28424 24165 4852 20798 5803 18679 24588 12238 25786 28622 19900 101 25922 2...
output:
642071982
result:
wrong answer 1st lines differ - expected: '18923', found: '642071982'
Test #5:
score: 0
Wrong Answer
time: 67ms
memory: 4328kb
input:
100000 100000 15043 9299 7163 25384 24996 3803 24356 12466 22073 12987 8931 14997 3951 32704 23076 8...
output:
426146300
result:
wrong answer 1st lines differ - expected: '754347097', found: '426146300'
Test #6:
score: 0
Wrong Answer
time: 63ms
memory: 4328kb
input:
100000 100000 14736 16956 19864 23894 29403 5507 12182 6188 17192 14440 18618 3970 15396 15037 23334...
output:
444883269
result:
wrong answer 1st lines differ - expected: '17008', found: '444883269'
Test #7:
score: 0
Wrong Answer
time: 25ms
memory: 2764kb
input:
50000 50000 17799 29763 25337 21321 1391 31852 27418 28753 18524 14044 15976 18893 12274 22834 11348...
output:
95803178
result:
wrong answer 1st lines differ - expected: '19498', found: '95803178'
Test #8:
score: 0
Wrong Answer
time: 31ms
memory: 2768kb
input:
50000 50000 10654 14956 14287 25326 8102 30579 11682 23553 272 22672 14460 30241 13026 12738 4912 72...
output:
81538007
result:
wrong answer 1st lines differ - expected: '717018991', found: '81538007'
Test #9:
score: 0
Wrong Answer
time: 57ms
memory: 4012kb
input:
90000 90000 29538 28214 24706 30393 27759 9002 13458 10243 15713 14881 10630 5593 7942 24578 29370 1...
output:
183708671
result:
wrong answer 1st lines differ - expected: '738835738', found: '183708671'
Test #10:
score: 0
Wrong Answer
time: 68ms
memory: 4328kb
input:
100000 100000 23515 49 31372 25112 16779 21279 30735 32743 14678 15189 1763 23114 32215 14873 20487 ...
output:
312617722
result:
wrong answer 1st lines differ - expected: '576735050', found: '312617722'
