Submission #3448350
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> i_i; typedef pair<ll, i_i> i_i_i; #define EPS (1e-7) #define INF (1e9) #define PI (acos(-1)) //const ll mod = 1000000007; struct UnionFind { vector<int> par; vector<int> rank; UnionFind(int n = 1) { init(n); } void init(int n = 1) { par.resize(n + 1); rank.resize(n + 1); for (int i = 0; i <= n; ++i) par[i] = i, rank[i] = 0; } int root(int x) { if (par[x] == x) { return x; } else { int r = root(par[x]); return par[x] = r; } } bool issame(int x, int y) { return root(x) == root(y); } bool merge(int x, int y) { x = root(x); y = root(y); if (x == y) return false; if (rank[x] < rank[y]) swap(x, y); if (rank[x] == rank[y]) ++rank[x]; par[y] = x; return true; } }; int main() { //cout.precision(10); UnionFind uni(200500); int n, m, k; vector<i_i_i> edges; cin >> n >> m >> k; if(k == 1){ cout << 0 << endl; return 0; } int c[100200]; for(int i = 1; i <= n; i++){ cin >> c[i]; } for(int i = 1; i <= m; i++){ int a, b; ll w; cin >> a >> b >> w; edges.push_back({w, {a, b}}); } ll ans = 0; sort(edges.begin(), edges.end()); int components = k; for(int i = 0; i < edges.size(); i++){ i_i_i now = edges[i]; int ca = c[now.second.first]; int cb = c[now.second.second]; int cost = now.first; if(ca == 0){ ca = now.second.first + 100000; } if(cb == 0){ cb = now.second.second + 100000; } if(uni.issame(ca, cb)) continue; uni.merge(ca, cb); components--; ans += cost; if(components == 1){ cout << ans << endl; return 0; } } cout << -1 << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Colorful MST |
User | kort0n |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 2129 Byte |
Status | AC |
Exec Time | 127 ms |
Memory | 4340 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 | 2 ms | 1792 KB |
00_example_02.txt | AC | 2 ms | 1792 KB |
00_example_03.txt | AC | 2 ms | 1792 KB |
00_example_04.txt | AC | 2 ms | 1792 KB |
s1_01.txt | AC | 2 ms | 1792 KB |
s1_02.txt | AC | 124 ms | 4340 KB |
s1_03.txt | AC | 2 ms | 1792 KB |
s1_04.txt | AC | 2 ms | 1792 KB |
s1_05.txt | AC | 67 ms | 3320 KB |
s1_06.txt | AC | 125 ms | 4340 KB |
s2_07.txt | AC | 18 ms | 2304 KB |
s2_08.txt | AC | 127 ms | 4340 KB |
s2_09.txt | AC | 94 ms | 4212 KB |
s2_10.txt | AC | 88 ms | 4212 KB |
s2_11.txt | AC | 119 ms | 4340 KB |
s2_12.txt | AC | 118 ms | 4340 KB |
s3_13.txt | AC | 16 ms | 2304 KB |
s3_14.txt | AC | 119 ms | 4340 KB |
s3_15.txt | AC | 91 ms | 4212 KB |
s3_16.txt | AC | 85 ms | 4212 KB |
s3_17.txt | AC | 112 ms | 4340 KB |
s3_18.txt | AC | 109 ms | 4340 KB |
s4_19.txt | AC | 17 ms | 2304 KB |
s4_20.txt | AC | 117 ms | 4340 KB |
s4_21.txt | AC | 93 ms | 4212 KB |
s4_22.txt | AC | 90 ms | 4212 KB |
s4_23.txt | AC | 120 ms | 4340 KB |
s4_24.txt | AC | 118 ms | 4340 KB |