Submission #2072438
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount
#define INF 1e16
struct UnionFind{
vector<int> v;
UnionFind(int n) : v(n, -1) {}
void init(){ for(int i = 0;i < v.size();i++)v[i]=-1; }
int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false;
if (-v[x] < -v[y]) swap(x, y);
v[x] += v[y]; v[y] = x;
return true;
}
bool root(int x) { return v[x] < 0; }
bool same(int x, int y) { return find(x) == find(y); }
int size(int x) { return -v[find(x)]; }
};
struct edge{
ll f,t,c;
};
bool operator<(const edge& a,const edge& b){return a.c < b.c;}
ll n,m,k;
ll col[101010];
vector<edge> es;
int main(){
cin>>n>>m>>k;
rep(i,n){
cin>>col[i];
col[i]--;
}
ll crtidx=k;
rep(i,n)if(col[i]==-1)col[i]=crtidx++;
rep(i,m){
ll a,b,c;
cin>>a>>b>>c;
a--; b--;
a=col[a];
b=col[b];
es.push_back((edge){a,b,c});
}
ll res=0,en=0;
UnionFind uf(crtidx);
sort(all(es));
rep(i,m){
edge e=es[i];
ll u=e.f,v=e.t;
if(uf.same(u,v))continue;
uf.unite(u,v);
res+=e.c;
en++;
if(en>=k-1)break;
}
if(en<k-1)cout<<-1<<endl;
else cout<<res<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Colorful MST |
User |
yamad |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
1826 Byte |
Status |
AC |
Exec Time |
125 ms |
Memory |
5620 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 |
121 ms |
4212 KB |
s1_03.txt |
AC |
1 ms |
256 KB |
s1_04.txt |
AC |
1 ms |
256 KB |
s1_05.txt |
AC |
66 ms |
2680 KB |
s1_06.txt |
AC |
122 ms |
5620 KB |
s2_07.txt |
AC |
17 ms |
960 KB |
s2_08.txt |
AC |
125 ms |
4212 KB |
s2_09.txt |
AC |
94 ms |
4596 KB |
s2_10.txt |
AC |
88 ms |
3828 KB |
s2_11.txt |
AC |
118 ms |
5364 KB |
s2_12.txt |
AC |
118 ms |
4980 KB |
s3_13.txt |
AC |
15 ms |
960 KB |
s3_14.txt |
AC |
111 ms |
5236 KB |
s3_15.txt |
AC |
89 ms |
3828 KB |
s3_16.txt |
AC |
84 ms |
3828 KB |
s3_17.txt |
AC |
109 ms |
4852 KB |
s3_18.txt |
AC |
108 ms |
4212 KB |
s4_19.txt |
AC |
16 ms |
960 KB |
s4_20.txt |
AC |
116 ms |
5364 KB |
s4_21.txt |
AC |
93 ms |
3828 KB |
s4_22.txt |
AC |
88 ms |
3828 KB |
s4_23.txt |
AC |
118 ms |
5236 KB |
s4_24.txt |
AC |
116 ms |
5620 KB |