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
AC × 4
AC × 7
AC × 12
AC × 7
AC × 28
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