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 |
|
|
|
|
|
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 |