Submission #3010154
Source Code Expand
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
using namespace std;
#ifdef DEB
#define dump(x) cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif
template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }
typedef long long int lint;
typedef pair<int,int> pi;
namespace std{
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
out<<'('<<a.fr<<','<<a.sc<<')';
return out;
}
}
struct uf{
static const int MAXN=200005;
int par[MAXN];
int size[MAXN];
void init(){
memset(par,-1,sizeof(par));
REP(i,MAXN) size[i]=1;
}
int root(int a){
if(par[a]==-1) return a;
return par[a]=root(par[a]);
}
void unite(int a,int b){
a=root(a);b=root(b);
if(a==b) return;
if(size[a]<size[b]) swap(a,b);
par[b]=a;
size[a]+=size[b];
}
bool same(int a,int b){
return root(a)==root(b);
}
};
uf u;
int n,m,K;
int col[100005];
pair<int,pi> es[100005];
int main(){
cin>>n>>m>>K;
int K2=K;
REP(i,n){
scanf("%d",&col[i]);
--col[i];
if(col[i]==-1) col[i]=K2++;
}
REP(i,m){
int a,b,w;scanf("%d%d%d",&a,&b,&w);
--a;--b;
int ca=col[a],cb=col[b];
es[i]={w,{ca,cb}};
}
sort(es,es+m);
u.init();
int comp=K2;
int uni=0;
lint tot=0;
lint res=-1;
REP(i,m) {
if(!u.same(es[i].sc.fr,es[i].sc.sc)){
u.unite(es[i].sc.fr,es[i].sc.sc);
--comp;
++uni;
tot+=es[i].fr;
if(uni==K-1){
res=tot;
break;
}
}
}
cout<<res<<endl;
return 0;
}
Submission Info
Submission Time
2018-08-15 12:08:48+0900
Task
A - Colorful MST
User
fxt
Language
C++ (GCC 5.4.1)
Score
700
Code Size
2383 Byte
Status
AC
Exec Time
45 ms
Memory
3328 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:87:21: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
es[i]={w,{ca,cb}};
^
./Main.cpp:87:10: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
es[i]={w,{ca,cb}};
^
./Main.cpp:87:10: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
./Main.cpp:79:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&col[i]);
^
./Main.cpp:84:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int a,b,w;scanf("%d%d%d",&a,&b,&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
2 ms
2944 KB
00_example_02.txt
AC
2 ms
2944 KB
00_example_03.txt
AC
2 ms
2944 KB
00_example_04.txt
AC
2 ms
2944 KB
s1_01.txt
AC
3 ms
2944 KB
s1_02.txt
AC
45 ms
3328 KB
s1_03.txt
AC
2 ms
2944 KB
s1_04.txt
AC
2 ms
2944 KB
s1_05.txt
AC
25 ms
3328 KB
s1_06.txt
AC
45 ms
3328 KB
s2_07.txt
AC
8 ms
3072 KB
s2_08.txt
AC
45 ms
3328 KB
s2_09.txt
AC
34 ms
3200 KB
s2_10.txt
AC
32 ms
3200 KB
s2_11.txt
AC
44 ms
3328 KB
s2_12.txt
AC
43 ms
3328 KB
s3_13.txt
AC
8 ms
3072 KB
s3_14.txt
AC
43 ms
3328 KB
s3_15.txt
AC
34 ms
3200 KB
s3_16.txt
AC
32 ms
3200 KB
s3_17.txt
AC
43 ms
3328 KB
s3_18.txt
AC
42 ms
3328 KB
s4_19.txt
AC
8 ms
3072 KB
s4_20.txt
AC
43 ms
3328 KB
s4_21.txt
AC
35 ms
3200 KB
s4_22.txt
AC
33 ms
3200 KB
s4_23.txt
AC
45 ms
3328 KB
s4_24.txt
AC
44 ms
3328 KB