Submission #3217443


Source Code Expand

import java.io.IOException; 
import java.io.InputStream; 
import java.io.PrintWriter; 
import java.util.*; 
 

class Main{ 

	static class UnionFind{
		int pare[];
		UnionFind(int n){
			pare = new int[n];
			Arrays.fill(pare, -1);
		}
		int root(int v){
			if(pare[v]<0)return v;
			return pare[v] = root(pare[v]);
		}
		boolean same(int u, int v){
			return root(u)==root(v);
		}
		boolean unite(int u, int v){
			u=root(u);
			v=root(v);
			if(u==v)return false;
			if(pare[u]<pare[v]){
				int tmp=u;u=v;v=tmp;
			}
			pare[v]+=pare[u];
			pare[u]=v;
			return true;
		}
	}
	static class Edge{
		int from, to;
		long cost;
		Edge(int f, int t, long c){from=f;to=t;cost=c;}
	}

	static void solve(){
		int n = ni(), m=ni(), k=ni();
		UnionFind uf = new UnionFind(n+k+1);
		int[] c = nia(n);
		int color = k+1;
		for(int i=0;i<n;++i)if(c[i]==0)c[i]=color++;

		PriorityQueue<Edge> que = new PriorityQueue<>((a,b)-> a.cost-b.cost<0 ? -1: 1);
		while(m-->0){
			int a=ni()-1, b=ni()-1;
			long w = nl();
			que.add(new Edge(a,b,w));
		}
		long ans =0;
		int cnt =0;
		while(!que.isEmpty() && cnt<k-1){
			Edge e = que.poll();
			if(!uf.unite(c[e.from], c[e.to]))continue;
			++cnt;
			ans += e.cost;
		}
		out.println((cnt==(k-1) ? ans: -1));
	} 
 
 
 
 
	 public static void main(String[] args){ 
		 solve(); 
		 out.flush(); 
	 } 
	 private static InputStream in = System.in; 
	 private static PrintWriter out = new PrintWriter(System.out); 
 
	 static boolean inrange(int y, int x, int h, int w){ 
		 return y>=0 && y<h && x>=0 && x<w; 
	 } 
	 @SuppressWarnings("unchecked") 
	 static<T extends Comparable> int lower_bound(List<T> list, T key){ 
		 int lower=-1;int upper=list.size(); 
		 while(upper - lower>1){ 
		 int center =(upper+lower)/2; 
		 if(list.get(center).compareTo(key)>=0)upper=center; 
		 else lower=center; 
		 } 
		 return upper; 
	 } 
	 @SuppressWarnings("unchecked") 
	 static <T extends Comparable> int upper_bound(List<T> list, T key){ 
		 int lower=-1;int upper=list.size(); 
		 while(upper-lower >1){ 
		 int center=(upper+lower)/2; 
		 if(list.get(center).compareTo(key)>0)upper=center; 
		 else lower=center; 
		 } 
		 return upper; 
	 } 
	 @SuppressWarnings("unchecked") 
	 static <T extends Comparable> boolean next_permutation(List<T> list){ 
		 int lastIndex = list.size()-2; 
		 while(lastIndex>=0 && list.get(lastIndex).compareTo(list.get(lastIndex+1))>=0)--lastIndex; 
		 if(lastIndex<0)return false; 
		 int swapIndex = list.size()-1; 
		 while(list.get(lastIndex).compareTo(list.get(swapIndex))>=0)swapIndex--; 
		 T tmp = list.get(lastIndex); 
		 list.set(lastIndex++, list.get(swapIndex)); 
		 list.set(swapIndex, tmp); 
		 swapIndex = list.size()-1; 
		 while(lastIndex<swapIndex){ 
		 tmp = list.get(lastIndex); 
		 list.set(lastIndex, list.get(swapIndex)); 
		 list.set(swapIndex, tmp); 
		 ++lastIndex;--swapIndex; 
		 } 
		 return true; 
	 } 
	 private static final byte[] buffer = new byte[1<<15]; 
	 private static int ptr = 0; 
	 private static int buflen = 0; 
	 private static boolean hasNextByte(){ 
		 if(ptr<buflen)return true; 
		 ptr = 0; 
		 try{ 
			 buflen = in.read(buffer); 
		 } catch (IOException e){ 
			 e.printStackTrace(); 
		 } 
		 return buflen>0; 
	 } 
	 private static int readByte(){ if(hasNextByte()) return buffer[ptr++]; else return -1;} 
	 private static boolean isSpaceChar(int c){ return !(33<=c && c<=126);} 
	 private static int skip(){int res; while((res=readByte())!=-1 && isSpaceChar(res)); return res;} 
 
	 private static double nd(){ return Double.parseDouble(ns()); } 
	 private static char nc(){ return (char)skip(); } 
	 private static String ns(){ 
		 StringBuilder sb = new StringBuilder(); 
		 for(int b=skip();!isSpaceChar(b);b=readByte())sb.append((char)b); 
		 return sb.toString(); 
	 } 
	 private static int[] nia(int n){ 
		 int[] res = new int[n]; 
		 for(int i=0;i<n;++i)res[i]=ni(); 
		 return res; 
	 } 
	 private static long[] nla(int n){ 
		 long[] res = new long[n]; 
		 for(int i=0;i<n;++i)res[i]=nl(); 
		 return res; 
	 } 
	 private static int ni(){ 
		 int res=0,b; 
		 boolean minus=false; 
		 while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-')); 
		 if(b=='-'){ 
			 minus=true; 
			 b=readByte(); 
		 } 
		 for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0'); 
		 return minus ? -res:res; 
	 } 
	 private static long nl(){ 
		 long res=0,b; 
		 boolean minus=false; 
		 while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-')); 
		 if(b=='-'){ 
			 minus=true; 
			 b=readByte(); 
		 } 
		 for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0'); 
		 return minus ? -res:res; 
	} 
} 

Submission Info

Submission Time
Task A - Colorful MST
User inmir
Language Java8 (OpenJDK 1.8.0)
Score 700
Code Size 4775 Byte
Status AC
Exec Time 309 ms
Memory 34504 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 150 ms 26196 KB
00_example_02.txt AC 149 ms 25040 KB
00_example_03.txt AC 150 ms 25164 KB
00_example_04.txt AC 146 ms 26068 KB
s1_01.txt AC 158 ms 25420 KB
s1_02.txt AC 309 ms 32588 KB
s1_03.txt AC 155 ms 23764 KB
s1_04.txt AC 145 ms 25940 KB
s1_05.txt AC 241 ms 29964 KB
s1_06.txt AC 299 ms 30160 KB
s2_07.txt AC 196 ms 26196 KB
s2_08.txt AC 288 ms 34504 KB
s2_09.txt AC 197 ms 29908 KB
s2_10.txt AC 187 ms 32084 KB
s2_11.txt AC 252 ms 29952 KB
s2_12.txt AC 233 ms 28044 KB
s3_13.txt AC 190 ms 26068 KB
s3_14.txt AC 268 ms 30676 KB
s3_15.txt AC 201 ms 29140 KB
s3_16.txt AC 233 ms 30728 KB
s3_17.txt AC 287 ms 33168 KB
s3_18.txt AC 239 ms 33532 KB
s4_19.txt AC 192 ms 23376 KB
s4_20.txt AC 228 ms 28108 KB
s4_21.txt AC 208 ms 30804 KB
s4_22.txt AC 231 ms 29424 KB
s4_23.txt AC 290 ms 33100 KB
s4_24.txt AC 252 ms 29120 KB