Submission #2901951
Source Code Expand
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define revv(V) reverse(allv(V))
#define sz(V) ((int)(V).size())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 100005;
const int MAXM = 100005;
const int MAXK = 100005;
int A[MAXN];
int B[MAXM], C[MAXM], D[MAXM], O[MAXM];
int ud[MAXK*2];
ll Ans; int AnsC;
int N, M, K;
int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }
int main() {
ios::sync_with_stdio(false);
cin >> N >> M >> K;
for(int i = 1; i <= N; i++) cin >> A[i];
for(int i = 1; i <= M; i++) cin >> B[i] >> C[i] >> D[i];
iota(O, O+M+1, 0);
sort(O+1, O+M+1, [&](int a, int b) { return D[a] < D[b]; });
iota(ud, ud+MAXK*2, 0);
for(int oi = 1, i, a, b, c; oi <= M; oi++) {
i = O[oi];
a = A[B[i]]; b = A[C[i]]; c = D[i];
if(!a) a = MAXK + B[i];
if(!b) b = MAXK + C[i];
if(uf(a) == uf(b)) continue;
AnsC++; uf(a, b);
Ans += c;
if(AnsC == K-1) break;
}
printf("%lld\n", AnsC == K-1 ? Ans : -1);
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Colorful MST |
User |
youngyojun |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
1411 Byte |
Status |
AC |
Exec Time |
51 ms |
Memory |
2944 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 |
1024 KB |
00_example_02.txt |
AC |
2 ms |
1024 KB |
00_example_03.txt |
AC |
1 ms |
1024 KB |
00_example_04.txt |
AC |
2 ms |
1024 KB |
s1_01.txt |
AC |
1 ms |
1024 KB |
s1_02.txt |
AC |
49 ms |
2944 KB |
s1_03.txt |
AC |
2 ms |
1024 KB |
s1_04.txt |
AC |
1 ms |
1024 KB |
s1_05.txt |
AC |
24 ms |
2048 KB |
s1_06.txt |
AC |
49 ms |
2944 KB |
s2_07.txt |
AC |
8 ms |
1280 KB |
s2_08.txt |
AC |
51 ms |
2944 KB |
s2_09.txt |
AC |
36 ms |
2688 KB |
s2_10.txt |
AC |
33 ms |
2560 KB |
s2_11.txt |
AC |
46 ms |
2944 KB |
s2_12.txt |
AC |
44 ms |
2944 KB |
s3_13.txt |
AC |
7 ms |
1280 KB |
s3_14.txt |
AC |
48 ms |
2944 KB |
s3_15.txt |
AC |
34 ms |
2688 KB |
s3_16.txt |
AC |
34 ms |
2560 KB |
s3_17.txt |
AC |
44 ms |
2944 KB |
s3_18.txt |
AC |
42 ms |
2944 KB |
s4_19.txt |
AC |
8 ms |
1280 KB |
s4_20.txt |
AC |
44 ms |
2944 KB |
s4_21.txt |
AC |
36 ms |
2688 KB |
s4_22.txt |
AC |
37 ms |
2560 KB |
s4_23.txt |
AC |
50 ms |
2944 KB |
s4_24.txt |
AC |
45 ms |
2944 KB |