Submission #2547262
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
struct UnionFind{
Int n;
vector<Int> r,p;
UnionFind(){}
UnionFind(Int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}
Int find(Int x){
return (x==p[x]?x:p[x]=find(p[x]));
}
bool same(Int x,Int y){
return find(x)==find(y);
}
void unite(Int x,Int y){
x=find(x);y=find(y);
if(x==y) return;
if(r[x]<r[y]) swap(x,y);
r[x]+=r[y];
p[y]=x;
}
};
//INSERT ABOVE HERE
signed main(){
Int n,m,k;
cin>>n>>m>>k;
vector<Int> c(n);
for(Int i=0;i<n;i++) cin>>c[i];
using T = tuple<Int, Int, Int>;
vector<T> v;
for(Int i=0;i<m;i++){
Int a,b,w;
cin>>a>>b>>w;
a--;b--;
v.emplace_back(w,a,b);
}
sort(v.begin(),v.end());
Int ans=0,cnt=1;
UnionFind uf(n+k);
for(Int i=0;i<n;i++){
c[i]--;
if(~c[i]) uf.unite(i,n+c[i]);
else cnt++;
}
priority_queue<Int> pq;
for(Int i=0;i<m;i++){
Int w,a,b;
tie(w,a,b)=v[i];
if(uf.same(a,b)) continue;
ans+=w;
uf.unite(a,b);
pq.emplace(w);
}
for(Int i=0;i<n+k;i++)
if(uf.find(i)==i) cnt--;
while(cnt>0){
ans-=pq.top();pq.pop();
cnt--;
}
if(cnt<0) ans=-1;
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Colorful MST |
User |
beet |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
1302 Byte |
Status |
AC |
Exec Time |
135 ms |
Memory |
8560 KB |
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 |
129 ms |
8560 KB |
s1_03.txt |
AC |
1 ms |
256 KB |
s1_04.txt |
AC |
1 ms |
256 KB |
s1_05.txt |
AC |
70 ms |
5876 KB |
s1_06.txt |
AC |
129 ms |
8304 KB |
s2_07.txt |
AC |
18 ms |
1276 KB |
s2_08.txt |
AC |
135 ms |
7408 KB |
s2_09.txt |
AC |
95 ms |
3828 KB |
s2_10.txt |
AC |
89 ms |
3828 KB |
s2_11.txt |
AC |
122 ms |
5744 KB |
s2_12.txt |
AC |
123 ms |
5108 KB |
s3_13.txt |
AC |
16 ms |
1404 KB |
s3_14.txt |
AC |
117 ms |
8176 KB |
s3_15.txt |
AC |
96 ms |
5104 KB |
s3_16.txt |
AC |
89 ms |
4592 KB |
s3_17.txt |
AC |
117 ms |
8304 KB |
s3_18.txt |
AC |
120 ms |
7280 KB |
s4_19.txt |
AC |
17 ms |
1276 KB |
s4_20.txt |
AC |
130 ms |
6256 KB |
s4_21.txt |
AC |
97 ms |
4208 KB |
s4_22.txt |
AC |
92 ms |
4464 KB |
s4_23.txt |
AC |
127 ms |
8176 KB |
s4_24.txt |
AC |
125 ms |
6512 KB |