Submission #2477470
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5;
vector<int> c(N);
vector<int> used(N);
vector<int> gg[N];
int n, m, k;
void dfs(int i, int &un) {
used[i] = 1;
if(i < n && c[i] == 0) un++;
for(int j : gg[i]) if(!used[j]) {
dfs(j, un);
}
}
/// --- Union Find Library {{{ ///
struct UF {
int n;
vector<int> par, rank;
UF(int n): n(n), par(n, -1), rank(n, 0) {}
int find(int x) {
return par[x] < 0 ? x : par[x] = find(par[x]);
}
int size(int x) {
return -par[find(x)];
}
bool same(int a, int b) {
return find(a) == find(b);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if(a == b) return;
if(rank[a] > rank[b]) swap(a, b);
par[b] += par[a];
par[a] = b;
if(rank[a] == rank[b]) rank[b]++;
}
};
/// }}}--- ///
vector<tuple<int, int, int>> g;
ll solve() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m >> k;
set<int> cols;
for(int i = 0; i < n; i++) {
cin >> c[i];
if(c[i] != 0) cols.emplace(c[i]);
}
for(int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
a--; b--;
gg[a].emplace_back(b);
gg[b].emplace_back(a);
g.emplace_back(w, a, b);
if(c[a]) g.emplace_back(0, a, n + c[a]);
if(c[b]) g.emplace_back(0, b, n + c[b]);
}
int forests = 0;
int no = 0;
int fre = 0;
for(int i = 0; i < n; i++) if(!used[i]) {
forests++;
int x = 0;
dfs(i, x);
if(x == 0) no++;
fre += x;
// cerr << "ref = " << fre << endl;
}
// cerr << forests << endl;
// cerr << no << endl;
// << k - cols.size() << endl;
if(no >= 2) return -1;
if(fre < forests - 1) return -1;
if(fre < k - cols.size()) return -1;
sort(begin(g), end(g));
UF uf(n + k + 10);
int cnt = 0;
ll ans = 0;
for(auto e : g) {
int w = get<0>(e), a = get<1>(e), b = get<2>(e);
if(uf.same(a, b)) continue;
uf.unite(a, b);
if(w) cnt++, ans += w;
if(cnt == k - 1) break;
}
return ans;
}
int main() {
cout << solve() << endl;
}
Submission Info
Submission Time |
|
Task |
A - Colorful MST |
User |
luma |
Language |
C++14 (GCC 5.4.1) |
Score |
200 |
Code Size |
2136 Byte |
Status |
WA |
Exec Time |
109 ms |
Memory |
21296 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 |
4 ms |
6528 KB |
00_example_02.txt |
WA |
4 ms |
6528 KB |
00_example_03.txt |
AC |
4 ms |
6528 KB |
00_example_04.txt |
AC |
4 ms |
6528 KB |
s1_01.txt |
AC |
4 ms |
6528 KB |
s1_02.txt |
AC |
89 ms |
21040 KB |
s1_03.txt |
AC |
4 ms |
6528 KB |
s1_04.txt |
AC |
4 ms |
6528 KB |
s1_05.txt |
AC |
59 ms |
14388 KB |
s1_06.txt |
AC |
89 ms |
21296 KB |
s2_07.txt |
AC |
14 ms |
8124 KB |
s2_08.txt |
AC |
91 ms |
18864 KB |
s2_09.txt |
AC |
80 ms |
15024 KB |
s2_10.txt |
AC |
73 ms |
12336 KB |
s2_11.txt |
AC |
109 ms |
16304 KB |
s2_12.txt |
AC |
107 ms |
16176 KB |
s3_13.txt |
AC |
12 ms |
7332 KB |
s3_14.txt |
WA |
69 ms |
12852 KB |
s3_15.txt |
AC |
53 ms |
10804 KB |
s3_16.txt |
AC |
51 ms |
10676 KB |
s3_17.txt |
AC |
68 ms |
12468 KB |
s3_18.txt |
AC |
65 ms |
11956 KB |
s4_19.txt |
WA |
13 ms |
7740 KB |
s4_20.txt |
WA |
80 ms |
14128 KB |
s4_21.txt |
AC |
77 ms |
12848 KB |
s4_22.txt |
AC |
74 ms |
12976 KB |
s4_23.txt |
AC |
81 ms |
14896 KB |
s4_24.txt |
AC |
106 ms |
15024 KB |