Submission #1840504
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
const int UF_MAX = 200010;
class UF{
int x[UF_MAX];
public:
UF(){
for(int i = 0 ; i < UF_MAX ; ++i) x[i] = -1;
}
void Union(int a , int b){
int s = a;
int t = b;
while(x[s] > -1) s = x[s];
while(x[t] > -1) t = x[t];
if(s != t){
if(x[s] < x[t]){
x[s] += x[t];
x[t] = s;
} else {
x[t] += x[s];
x[s] = t;
}
}
if(s != a) x[a] = s;
if(t != b) x[b] = t;
}
bool Find(int a , int b){
int s = a;
int t = b;
while(x[s] > -1) s = x[s];
while(x[t] > -1) t = x[t];
if(s != a) x[a] = s;
if(t != b) x[b] = t;
return s == t;
}
int Count(int a){
int b = 0;
for(int i = 0 ; i < a ; ++i) if(x[i] < 0) ++b;
return b;
}
} uf;
const int MC = 100010;
int N,M;
int K;
int a[MC],b[MC],w[MC];
int c[MC];
int s[MC];
int main(){
cin >> N >> M >> K;
repp(i,1,N+1){
cin >> c[i];
}
repp(i,0,M){
cin >> a[i] >> b[i] >> w[i];
s[i] = i;
}
sort(s,s+M,[&](const int x , const int y){return w[x] < w[y];});
LL ans = 0;
int z = 0;
repp(i,0,M){
if(z==K-1) break;
if(c[a[s[i]]] == 0 || c[b[s[i]]] == 0){
if(c[a[s[i]]] != 0){
if(uf.Find(c[a[s[i]]],K+b[s[i]])) continue;
uf.Union(c[a[s[i]]],K+b[s[i]]);
} else if(c[b[s[i]]] != 0){
if(uf.Find(c[b[s[i]]],K+a[s[i]])) continue;
uf.Union(c[b[s[i]]],K+a[s[i]]);
}
ans += w[s[i]];
++z;
continue;
}
if(uf.Find(c[a[s[i]]],c[b[s[i]]])) continue;
uf.Union(c[a[s[i]]],c[b[s[i]]]);
ans += w[s[i]];
++z;
}
cout << (z<K-1?-1:ans) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Colorful MST |
User |
PIandS |
Language |
C++14 (GCC 5.4.1) |
Score |
200 |
Code Size |
2127 Byte |
Status |
WA |
Exec Time |
157 ms |
Memory |
2944 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Subtask4 |
Score / Max Score |
0 / 0 |
100 / 100 |
100 / 100 |
0 / 200 |
0 / 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 |
1024 KB |
00_example_02.txt |
AC |
2 ms |
1024 KB |
00_example_03.txt |
AC |
2 ms |
1024 KB |
00_example_04.txt |
AC |
2 ms |
1024 KB |
s1_01.txt |
AC |
2 ms |
1024 KB |
s1_02.txt |
AC |
155 ms |
2944 KB |
s1_03.txt |
AC |
2 ms |
1024 KB |
s1_04.txt |
AC |
2 ms |
1024 KB |
s1_05.txt |
AC |
82 ms |
2048 KB |
s1_06.txt |
AC |
155 ms |
2944 KB |
s2_07.txt |
AC |
22 ms |
1280 KB |
s2_08.txt |
AC |
157 ms |
2944 KB |
s2_09.txt |
AC |
118 ms |
2560 KB |
s2_10.txt |
AC |
108 ms |
2560 KB |
s2_11.txt |
AC |
149 ms |
2944 KB |
s2_12.txt |
AC |
146 ms |
2944 KB |
s3_13.txt |
WA |
19 ms |
1280 KB |
s3_14.txt |
WA |
134 ms |
2944 KB |
s3_15.txt |
AC |
114 ms |
2560 KB |
s3_16.txt |
WA |
102 ms |
2560 KB |
s3_17.txt |
WA |
137 ms |
2944 KB |
s3_18.txt |
AC |
131 ms |
2944 KB |
s4_19.txt |
WA |
20 ms |
1280 KB |
s4_20.txt |
WA |
144 ms |
2944 KB |
s4_21.txt |
WA |
118 ms |
2560 KB |
s4_22.txt |
WA |
109 ms |
2560 KB |
s4_23.txt |
AC |
151 ms |
2944 KB |
s4_24.txt |
WA |
145 ms |
2944 KB |