Submission #2902046
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<lint, int> pi;
const int MAXN = 200005;
struct disj{
int pa[MAXN];
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
void init(int n){
iota(pa, pa + n + 1, 0);
}
bool uni(int p, int q){
p = find(p);
q = find(q);
if(p == q) return 0;
pa[q] = p; return 1;
}
}disj;
struct edg{
int s, e, x;
bool operator<(const edg &e)const{
return x < e.x;
}
};
vector<edg> v;
int n, m, k, c[MAXN];
int main(){
scanf("%d %d %d",&n,&m,&k);
int cnt = k - 1;
for(int i=1; i<=n; i++){
scanf("%d",&c[i]);
if(c[i]) cnt++;
if(c[i]) v.push_back({i, c[i] + n, 0});
}
for(int i=1; i<=m; i++){
int s, e, x;
scanf("%d %d %d",&s,&e,&x);
v.push_back({s, e, x});
}
sort(v.begin(), v.end());
disj.init(n+k);
lint ans = 0;
for(auto &i : v){
if(disj.uni(i.s, i.e)){
ans += i.x;
cnt--;
if(cnt == 0) break;
}
}
if(cnt > 0) ans = -1;
cout << ans << endl;
}
Submission Info
Submission Time |
|
Task |
A - Colorful MST |
User |
koosaga |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
1041 Byte |
Status |
AC |
Exec Time |
50 ms |
Memory |
5364 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:34:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&n,&m,&k);
^
./Main.cpp:37:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&c[i]);
^
./Main.cpp:43:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&s,&e,&x);
^
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 |
47 ms |
4596 KB |
s1_03.txt |
AC |
1 ms |
256 KB |
s1_04.txt |
AC |
1 ms |
256 KB |
s1_05.txt |
AC |
27 ms |
3828 KB |
s1_06.txt |
AC |
48 ms |
3952 KB |
s2_07.txt |
AC |
8 ms |
892 KB |
s2_08.txt |
AC |
50 ms |
4980 KB |
s2_09.txt |
AC |
36 ms |
3700 KB |
s2_10.txt |
AC |
33 ms |
2164 KB |
s2_11.txt |
AC |
47 ms |
5364 KB |
s2_12.txt |
AC |
46 ms |
4724 KB |
s3_13.txt |
AC |
6 ms |
704 KB |
s3_14.txt |
AC |
43 ms |
2676 KB |
s3_15.txt |
AC |
33 ms |
2168 KB |
s3_16.txt |
AC |
31 ms |
2040 KB |
s3_17.txt |
AC |
41 ms |
2676 KB |
s3_18.txt |
AC |
40 ms |
2420 KB |
s4_19.txt |
AC |
7 ms |
892 KB |
s4_20.txt |
AC |
45 ms |
4468 KB |
s4_21.txt |
AC |
35 ms |
2292 KB |
s4_22.txt |
AC |
34 ms |
2164 KB |
s4_23.txt |
AC |
46 ms |
4596 KB |
s4_24.txt |
AC |
45 ms |
3828 KB |