Submission #1819899
Source Code Expand
#include<bits/stdc++.h>
#define maxn 100100
using namespace std;
struct edge{
int u,v,w;
void scan(){scanf("%d%d%d",&u,&v,&w);}
int operator<(const edge& e)const{return w<e.w;}
}d[maxn];
int n,m,k,c[maxn],f[maxn],g[maxn],l,r;
long long ans;
int find(int f[],int x){
return x==f[x]?x:f[x]=find(f,f[x]);
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i)scanf("%d",&c[i]);
for(int i=1;i<=m;++i)d[i].scan();
for(int i=1;i<=n;++i)f[i]=i,g[i]=i;
sort(d+1,d+m+1);
for(int i=1;i<=m&&k>1;++i){
int u=find(f,d[i].u),v=find(f,d[i].v),cu=c[u],cv=c[v];
if(u==v)continue;
f[u]=v,c[v]=cv?cv:cu;
if(cu&&cv){
int gc=find(g,cu),gv=find(g,cv);
if(gc==gv)continue;
g[gc]=gv,ans+=d[i].w,k--;
} else k--,ans+=d[i].w;
}
if(k>1)return puts("-1"),0;
printf("%lld",ans);
}
Submission Info
Submission Time
2017-12-01 21:12:00+0900
Task
A - Colorful MST
User
yfzcsc
Language
C++14 (GCC 5.4.1)
Score
700
Code Size
821 Byte
Status
AC
Exec Time
51 ms
Memory
2560 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:15:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&n,&m,&k);
^
./Main.cpp:16:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;++i)scanf("%d",&c[i]);
^
./Main.cpp: In member function ‘void edge::scan()’:
./Main.cpp:6:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
void scan(){scanf("%d%d%d",&u,&v,&w);}
^
Judge Result
Set Name
Sample
Subtask1
Subtask2
Subtask3
Subtask4
Score / Max Score
0 / 0
100 / 100
100 / 100
200 / 200
300 / 300
Status
Set Name
Test Cases
Sample
00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 00_example_04.txt
Subtask1
00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt
Subtask2
s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s2_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt
Subtask3
00_example_02.txt, s3_13.txt, s3_14.txt, s3_15.txt, s3_16.txt, s3_17.txt, s3_18.txt
Subtask4
00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 00_example_04.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s2_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s3_13.txt, s3_14.txt, s3_15.txt, s3_16.txt, s3_17.txt, s3_18.txt, s4_19.txt, s4_20.txt, s4_21.txt, s4_22.txt, s4_23.txt, s4_24.txt
Case Name
Status
Exec Time
Memory
00_example_01.txt
AC
1 ms
256 KB
00_example_02.txt
AC
1 ms
256 KB
00_example_03.txt
AC
1 ms
256 KB
00_example_04.txt
AC
1 ms
256 KB
s1_01.txt
AC
1 ms
256 KB
s1_02.txt
AC
46 ms
2560 KB
s1_03.txt
AC
1 ms
256 KB
s1_04.txt
AC
1 ms
256 KB
s1_05.txt
AC
24 ms
1920 KB
s1_06.txt
AC
46 ms
2560 KB
s2_07.txt
AC
7 ms
640 KB
s2_08.txt
AC
51 ms
2560 KB
s2_09.txt
AC
33 ms
1920 KB
s2_10.txt
AC
31 ms
1792 KB
s2_11.txt
AC
45 ms
2560 KB
s2_12.txt
AC
43 ms
2560 KB
s3_13.txt
AC
6 ms
640 KB
s3_14.txt
AC
43 ms
2560 KB
s3_15.txt
AC
32 ms
1920 KB
s3_16.txt
AC
31 ms
1792 KB
s3_17.txt
AC
44 ms
2560 KB
s3_18.txt
AC
40 ms
2560 KB
s4_19.txt
AC
7 ms
640 KB
s4_20.txt
AC
42 ms
2560 KB
s4_21.txt
AC
33 ms
1920 KB
s4_22.txt
AC
35 ms
1792 KB
s4_23.txt
AC
50 ms
2560 KB
s4_24.txt
AC
43 ms
2560 KB