Submission #1997327
Source Code Expand
#include <iostream> #include <vector> #include <algorithm> #include <tuple> using namespace std; class UnionFind { public: vector<long long>par; long long size_ = 0; void init(long long size__) { size_ = size__; par.resize(size_ + 1, -1); } long long root(long long x) { if (par[x] == -1) return x; par[x] = root(par[x]); return par[x]; } void unite(long long x, long long y) { x = root(x); y = root(y); if (x != y) par[y] = x; } bool same(long long x, long long y) { if (root(x) == root(y)) return true; return false; } }; long long n, m, k, a[100009], b[100009], c[100009], w[100009], col[100009], cntw, ret, sum; vector<int>x[100009]; vector<tuple<int, int, int>>L; void dfs(int pos) { if (col[pos] >= 1) return; col[pos] = cntw; for (int i = 0; i < x[pos].size(); i++) dfs(x[pos][i]); } int main() { cin >> n >> m >> k; for (int i = 1; i <= n; i++) cin >> c[i]; for (int i = 1; i <= m; i++) { cin >> a[i] >> b[i] >> w[i]; if (c[a[i]] == 1 && c[b[i]] == 1) { x[c[a[i]]].push_back(c[b[i]]); x[c[b[i]]].push_back(c[a[i]]); } } for (int i = 1; i <= k; i++) { if (col[i] >= 1) continue; cntw++; dfs(i); } for (int i = 1; i <= m; i++) { int p1 = a[i]; if (c[a[i]] >= 1) p1 = col[c[a[i]]]; else p1 = a[i] + n; int p2 = b[i]; if (c[b[i]] >= 1) p2 = col[c[b[i]]]; else p2 = b[i] + n; L.push_back(make_tuple(w[i], p1, p2)); } sort(L.begin(), L.end()); UnionFind UF; UF.init(2 * n + 2); for (int i = 0; i < L.size(); i++) { if (UF.same(get<1>(L[i]), get<2>(L[i])) == false && ret < cntw - 1) { ret++; sum += get<0>(L[i]); UF.unite(get<1>(L[i]), get<2>(L[i])); } } if (ret < cntw - 1) sum = -1; cout << sum << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Colorful MST |
User | E869120 |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1756 Byte |
Status | AC |
Exec Time | 132 ms |
Memory | 9332 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 | 3 ms | 6400 KB |
00_example_02.txt | AC | 3 ms | 6400 KB |
00_example_03.txt | AC | 3 ms | 6400 KB |
00_example_04.txt | AC | 3 ms | 6400 KB |
s1_01.txt | AC | 3 ms | 6400 KB |
s1_02.txt | AC | 128 ms | 9332 KB |
s1_03.txt | AC | 3 ms | 6400 KB |
s1_04.txt | AC | 3 ms | 6400 KB |
s1_05.txt | AC | 69 ms | 8568 KB |
s1_06.txt | AC | 128 ms | 9332 KB |
s2_07.txt | AC | 19 ms | 6976 KB |
s2_08.txt | AC | 132 ms | 9332 KB |
s2_09.txt | AC | 96 ms | 8436 KB |
s2_10.txt | AC | 90 ms | 8056 KB |
s2_11.txt | AC | 124 ms | 9332 KB |
s2_12.txt | AC | 123 ms | 9332 KB |
s3_13.txt | AC | 17 ms | 6976 KB |
s3_14.txt | AC | 116 ms | 9332 KB |
s3_15.txt | AC | 92 ms | 8436 KB |
s3_16.txt | AC | 89 ms | 8056 KB |
s3_17.txt | AC | 114 ms | 9332 KB |
s3_18.txt | AC | 116 ms | 9332 KB |
s4_19.txt | AC | 18 ms | 6976 KB |
s4_20.txt | AC | 122 ms | 9332 KB |
s4_21.txt | AC | 98 ms | 8436 KB |
s4_22.txt | AC | 93 ms | 8056 KB |
s4_23.txt | AC | 124 ms | 9332 KB |
s4_24.txt | AC | 124 ms | 9332 KB |