Submission #1840504


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int UF_MAX = 200010;

class UF{
	int x[UF_MAX];
	
public:
	
	UF(){
		for(int i = 0 ; i < UF_MAX ; ++i) x[i] = -1;
	}
	
	void Union(int a , int b){
		int s = a;
		int t = b;
		while(x[s] > -1) s = x[s];
		while(x[t] > -1) t = x[t];
		if(s != t){
			if(x[s] < x[t]){
				x[s] += x[t];
				x[t] = s;
			} else {
				x[t] += x[s];
				x[s] = t;
			}
		}
		if(s != a) x[a] = s;
		if(t != b) x[b] = t;
	}
	
	bool Find(int a , int b){
		int s = a;
		int t = b;
		while(x[s] > -1) s = x[s];
		while(x[t] > -1) t = x[t];
		if(s != a) x[a] = s;
		if(t != b) x[b] = t;
		return s == t;
	}
	
	int Count(int a){
		int b = 0;
		for(int i = 0 ; i < a ; ++i) if(x[i] < 0) ++b;
		return b;
	}
} uf;


const int MC = 100010;
int N,M;
int K;
int a[MC],b[MC],w[MC];
int c[MC];
int s[MC];

int main(){
	cin >> N >> M >> K;
	repp(i,1,N+1){
		cin >> c[i];
	}
	repp(i,0,M){
		cin >> a[i] >> b[i] >> w[i];
		s[i] = i;
	}
	sort(s,s+M,[&](const int x , const int y){return w[x] < w[y];});
	LL ans = 0;
	int z = 0;
	repp(i,0,M){
		if(z==K-1) break;
		if(c[a[s[i]]] == 0 || c[b[s[i]]] == 0){
			if(c[a[s[i]]] != 0){
				if(uf.Find(c[a[s[i]]],K+b[s[i]])) continue;
				uf.Union(c[a[s[i]]],K+b[s[i]]);
			} else if(c[b[s[i]]] != 0){
				if(uf.Find(c[b[s[i]]],K+a[s[i]])) continue;
				uf.Union(c[b[s[i]]],K+a[s[i]]);
			}
			ans += w[s[i]];
			++z;
			continue;
		}
		if(uf.Find(c[a[s[i]]],c[b[s[i]]])) continue;
		uf.Union(c[a[s[i]]],c[b[s[i]]]);
		ans += w[s[i]];
		++z;
	}
	cout << (z<K-1?-1:ans) << endl;
	return 0;
}

Submission Info

Submission Time
Task A - Colorful MST
User PIandS
Language C++14 (GCC 5.4.1)
Score 200
Code Size 2127 Byte
Status WA
Exec Time 157 ms
Memory 2944 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 0 / 0 100 / 100 100 / 100 0 / 200 0 / 300
Status
AC × 4
AC × 7
AC × 12
AC × 3
WA × 4
AC × 19
WA × 9
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 1024 KB
00_example_02.txt AC 2 ms 1024 KB
00_example_03.txt AC 2 ms 1024 KB
00_example_04.txt AC 2 ms 1024 KB
s1_01.txt AC 2 ms 1024 KB
s1_02.txt AC 155 ms 2944 KB
s1_03.txt AC 2 ms 1024 KB
s1_04.txt AC 2 ms 1024 KB
s1_05.txt AC 82 ms 2048 KB
s1_06.txt AC 155 ms 2944 KB
s2_07.txt AC 22 ms 1280 KB
s2_08.txt AC 157 ms 2944 KB
s2_09.txt AC 118 ms 2560 KB
s2_10.txt AC 108 ms 2560 KB
s2_11.txt AC 149 ms 2944 KB
s2_12.txt AC 146 ms 2944 KB
s3_13.txt WA 19 ms 1280 KB
s3_14.txt WA 134 ms 2944 KB
s3_15.txt AC 114 ms 2560 KB
s3_16.txt WA 102 ms 2560 KB
s3_17.txt WA 137 ms 2944 KB
s3_18.txt AC 131 ms 2944 KB
s4_19.txt WA 20 ms 1280 KB
s4_20.txt WA 144 ms 2944 KB
s4_21.txt WA 118 ms 2560 KB
s4_22.txt WA 109 ms 2560 KB
s4_23.txt AC 151 ms 2944 KB
s4_24.txt WA 145 ms 2944 KB