結果
問題 | No.556 仁義なきサルたち |
ユーザー | fal_rnd |
提出日時 | 2017-08-11 23:28:11 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 378 ms / 2,000 ms |
コード長 | 1,426 bytes |
コンパイル時間 | 4,035 ms |
コンパイル使用メモリ | 89,708 KB |
実行使用メモリ | 48,360 KB |
最終ジャッジ日時 | 2024-04-20 23:41:59 |
合計ジャッジ時間 | 8,453 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 117 ms
40,016 KB |
testcase_01 | AC | 138 ms
41,464 KB |
testcase_02 | AC | 130 ms
41,292 KB |
testcase_03 | AC | 120 ms
40,524 KB |
testcase_04 | AC | 122 ms
40,016 KB |
testcase_05 | AC | 155 ms
41,732 KB |
testcase_06 | AC | 158 ms
41,472 KB |
testcase_07 | AC | 170 ms
41,760 KB |
testcase_08 | AC | 168 ms
41,688 KB |
testcase_09 | AC | 201 ms
42,232 KB |
testcase_10 | AC | 221 ms
43,048 KB |
testcase_11 | AC | 229 ms
42,880 KB |
testcase_12 | AC | 219 ms
42,732 KB |
testcase_13 | AC | 246 ms
42,812 KB |
testcase_14 | AC | 292 ms
46,544 KB |
testcase_15 | AC | 296 ms
47,708 KB |
testcase_16 | AC | 331 ms
45,572 KB |
testcase_17 | AC | 334 ms
47,584 KB |
testcase_18 | AC | 374 ms
48,216 KB |
testcase_19 | AC | 378 ms
46,900 KB |
testcase_20 | AC | 370 ms
48,360 KB |
testcase_21 | AC | 366 ms
48,032 KB |
ソースコード
import java.util.Arrays; import java.util.Scanner; import java.util.stream.IntStream; public class Main{ static IntStream REPS(int v){return IntStream.range(0,v);} static IntStream REPS(int l,int r){return IntStream.rangeClosed(l,r);} static IntStream INS(int n) {return REPS(n).map(i->getInt());} static Scanner s=new Scanner(System.in); static int getInt(){return Integer.parseInt(s.next());} public static void main(String[]$){ int n=getInt(),q=getInt(); UF uf=new UF(n); for(int i=0;i<q;++i) { int a=getInt()-1,b=getInt()-1; int ga=uf.groupSize(a),gb=uf.groupSize(b); if(ga<gb){ uf.connect(b,a); }else if(ga>gb){ uf.connect(a,b); }else { int ra=uf.root(a),rb=uf.root(b); if(ra<rb) uf.connect(a,b); else uf.connect(b,a); } //System.out.println(Arrays.toString(uf.uni)); } REPS(n).map(i->uf.root(i)+1).forEach(System.out::println); } } class UF{ public int[] uni; public UF(int size){ uni=new int[size]; Arrays.fill(uni,-1); } public int root(int t){ if(uni[t]<0) return t; return uni[t]=root(uni[t]); } public boolean connect(int p,int c){ p=root(p); c=root(c); if(p==c) return false; if(uni[p]>uni[c]){ final int buf=c; c=p; p=buf; } uni[p]+=uni[c]; uni[c]=p; return true; } public boolean isConnected(int a,int b){ return root(a)==root(b); } public int groupSize(int t){ return -uni[root(t)]; } }