Submission #2902046


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<lint, int> pi;
const int MAXN = 200005;

struct disj{
	int pa[MAXN];
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	void init(int n){
		iota(pa, pa + n + 1, 0);
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}disj;

struct edg{
	int s, e, x;
	bool operator<(const edg &e)const{
		return x < e.x;
	}
};

vector<edg> v;
int n, m, k, c[MAXN];

int main(){
	scanf("%d %d %d",&n,&m,&k);
	int cnt = k - 1;
	for(int i=1; i<=n; i++){
		scanf("%d",&c[i]);
		if(c[i]) cnt++;
		if(c[i]) v.push_back({i, c[i] + n, 0});
	}
	for(int i=1; i<=m; i++){
		int s, e, x;
		scanf("%d %d %d",&s,&e,&x);
		v.push_back({s, e, x});
	}
	sort(v.begin(), v.end());
	disj.init(n+k);
	lint ans = 0;
	for(auto &i : v){
		if(disj.uni(i.s, i.e)){
			ans += i.x;
			cnt--;
			if(cnt == 0) break;
		}
	}
	if(cnt > 0) ans = -1;
	cout << ans << endl;
}

Submission Info

Submission Time
Task A - Colorful MST
User koosaga
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1041 Byte
Status AC
Exec Time 50 ms
Memory 5364 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:34:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&k);
                            ^
./Main.cpp:37:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&c[i]);
                    ^
./Main.cpp:43:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&s,&e,&x);
                             ^

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 1 ms 256 KB
00_example_02.txt AC 1 ms 256 KB
00_example_03.txt AC 1 ms 256 KB
00_example_04.txt AC 1 ms 256 KB
s1_01.txt AC 1 ms 256 KB
s1_02.txt AC 47 ms 4596 KB
s1_03.txt AC 1 ms 256 KB
s1_04.txt AC 1 ms 256 KB
s1_05.txt AC 27 ms 3828 KB
s1_06.txt AC 48 ms 3952 KB
s2_07.txt AC 8 ms 892 KB
s2_08.txt AC 50 ms 4980 KB
s2_09.txt AC 36 ms 3700 KB
s2_10.txt AC 33 ms 2164 KB
s2_11.txt AC 47 ms 5364 KB
s2_12.txt AC 46 ms 4724 KB
s3_13.txt AC 6 ms 704 KB
s3_14.txt AC 43 ms 2676 KB
s3_15.txt AC 33 ms 2168 KB
s3_16.txt AC 31 ms 2040 KB
s3_17.txt AC 41 ms 2676 KB
s3_18.txt AC 40 ms 2420 KB
s4_19.txt AC 7 ms 892 KB
s4_20.txt AC 45 ms 4468 KB
s4_21.txt AC 35 ms 2292 KB
s4_22.txt AC 34 ms 2164 KB
s4_23.txt AC 46 ms 4596 KB
s4_24.txt AC 45 ms 3828 KB