結果
問題 | No.2290 UnUnion Find |
ユーザー | viral8 |
提出日時 | 2023-05-06 11:15:25 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,995 ms / 2,000 ms |
コード長 | 1,098 bytes |
コンパイル時間 | 3,215 ms |
コンパイル使用メモリ | 77,148 KB |
実行使用メモリ | 60,780 KB |
最終ジャッジ日時 | 2024-11-23 20:32:07 |
合計ジャッジ時間 | 90,348 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 132 ms
41,244 KB |
testcase_01 | AC | 130 ms
41,132 KB |
testcase_02 | AC | 1,725 ms
57,496 KB |
testcase_03 | AC | 1,731 ms
59,188 KB |
testcase_04 | AC | 1,721 ms
59,860 KB |
testcase_05 | AC | 1,748 ms
59,916 KB |
testcase_06 | AC | 1,724 ms
59,772 KB |
testcase_07 | AC | 1,725 ms
59,676 KB |
testcase_08 | AC | 1,738 ms
58,928 KB |
testcase_09 | AC | 1,748 ms
60,040 KB |
testcase_10 | AC | 1,755 ms
59,720 KB |
testcase_11 | AC | 1,728 ms
60,568 KB |
testcase_12 | AC | 1,792 ms
60,476 KB |
testcase_13 | AC | 1,732 ms
59,092 KB |
testcase_14 | AC | 1,786 ms
59,764 KB |
testcase_15 | AC | 1,793 ms
58,900 KB |
testcase_16 | AC | 1,752 ms
59,120 KB |
testcase_17 | AC | 1,715 ms
59,544 KB |
testcase_18 | AC | 1,691 ms
60,200 KB |
testcase_19 | AC | 1,808 ms
60,492 KB |
testcase_20 | AC | 1,755 ms
60,428 KB |
testcase_21 | AC | 1,924 ms
59,332 KB |
testcase_22 | AC | 1,816 ms
59,580 KB |
testcase_23 | AC | 1,944 ms
59,460 KB |
testcase_24 | AC | 1,812 ms
60,104 KB |
testcase_25 | AC | 1,945 ms
59,900 KB |
testcase_26 | AC | 1,831 ms
60,024 KB |
testcase_27 | AC | 1,820 ms
59,972 KB |
testcase_28 | AC | 1,854 ms
59,680 KB |
testcase_29 | AC | 1,837 ms
60,024 KB |
testcase_30 | AC | 1,922 ms
59,088 KB |
testcase_31 | AC | 1,818 ms
59,908 KB |
testcase_32 | AC | 1,923 ms
59,224 KB |
testcase_33 | AC | 1,814 ms
59,516 KB |
testcase_34 | AC | 1,767 ms
60,780 KB |
testcase_35 | AC | 1,830 ms
60,152 KB |
testcase_36 | AC | 1,910 ms
59,060 KB |
testcase_37 | AC | 1,909 ms
59,416 KB |
testcase_38 | AC | 1,995 ms
59,556 KB |
testcase_39 | AC | 1,901 ms
59,628 KB |
testcase_40 | AC | 1,824 ms
60,052 KB |
testcase_41 | AC | 1,990 ms
59,348 KB |
testcase_42 | AC | 1,896 ms
59,704 KB |
testcase_43 | AC | 1,849 ms
59,712 KB |
testcase_44 | AC | 1,781 ms
59,868 KB |
testcase_45 | AC | 1,775 ms
59,728 KB |
testcase_46 | AC | 1,768 ms
59,832 KB |
ソースコード
import java.util.Scanner; import java.util.Arrays; class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int Q = sc.nextInt(); UnionFind uf = new UnionFind(N+1); while(Q-->0){ int q = sc.nextInt(); if(q==1){ int u = sc.nextInt(); int v = sc.nextInt(); uf.unite(u,v); } else{ int v = sc.nextInt(); int ans = uf.unUnitePoint(v); if(ans>N) ans = -1; System.out.println(ans); } } } } class UnionFind{ int[] par,unUnite; UnionFind(int N){ par = new int[N]; unUnite = new int[N]; Arrays.fill(par,-1); Arrays.fill(unUnite,1); unUnite[1] = 2; } int root(int x){ if(par[x]==-1) return x; return par[x] = root(par[x]); } void unite(int x,int y){ int rootX = root(x); int rootY = root(y); if(rootX==rootY) return; par[rootY] = rootX; check(rootY); check(rootX); } void check(int x){ int root = root(x); while(unUnite[root]<unUnite.length&&root==root(unUnite[root])) unUnite[root]++; } int unUnitePoint(int x){ return unUnite[root(x)]; } }