#832019 (Java21) No.1254 補強への架け橋

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	tenten
提出日時	2023-01-11 15:53:05
言語	Java21 (openjdk 21)
結果	AC
実行時間	1,223 ms / 2,000 ms
コード長	4,114 bytes
コンパイル時間	3,364 ms
コンパイル使用メモリ	86,032 KB
実行使用メモリ	111,632 KB
最終ジャッジ日時	2024-12-22 08:23:29
合計ジャッジ時間	47,727 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	59 ms 36,828 KB
testcase_01	AC	59 ms 36,836 KB
testcase_02	AC	59 ms 36,748 KB
testcase_03	AC	58 ms 37,200 KB
testcase_04	AC	60 ms 36,956 KB
testcase_05	AC	58 ms 36,932 KB
testcase_06	AC	58 ms 37,028 KB
testcase_07	AC	58 ms 36,736 KB
testcase_08	AC	57 ms 36,624 KB
testcase_09	AC	60 ms 36,624 KB
testcase_10	AC	60 ms 37,076 KB
testcase_11	AC	56 ms 36,804 KB
testcase_12	AC	59 ms 36,864 KB
testcase_13	AC	59 ms 36,936 KB
testcase_14	AC	60 ms 36,968 KB
testcase_15	AC	58 ms 37,104 KB
testcase_16	AC	62 ms 36,796 KB
testcase_17	AC	61 ms 37,096 KB
testcase_18	AC	56 ms 37,188 KB
testcase_19	AC	57 ms 36,996 KB
testcase_20	AC	61 ms 36,968 KB
testcase_21	AC	59 ms 37,080 KB
testcase_22	AC	62 ms 37,184 KB
testcase_23	AC	58 ms 36,932 KB
testcase_24	AC	62 ms 36,980 KB
testcase_25	AC	61 ms 36,804 KB
testcase_26	AC	61 ms 37,116 KB
testcase_27	AC	58 ms 36,980 KB
testcase_28	AC	62 ms 37,096 KB
testcase_29	AC	59 ms 36,864 KB
testcase_30	AC	58 ms 36,744 KB
testcase_31	AC	60 ms 36,756 KB
testcase_32	AC	60 ms 36,932 KB
testcase_33	AC	61 ms 37,180 KB
testcase_34	AC	60 ms 37,044 KB
testcase_35	AC	61 ms 37,104 KB
testcase_36	AC	60 ms 36,740 KB
testcase_37	AC	60 ms 36,864 KB
testcase_38	AC	58 ms 37,096 KB
testcase_39	AC	59 ms 37,044 KB
testcase_40	AC	61 ms 37,096 KB
testcase_41	AC	59 ms 36,916 KB
testcase_42	AC	59 ms 36,628 KB
testcase_43	AC	93 ms 38,264 KB
testcase_44	AC	71 ms 37,628 KB
testcase_45	AC	68 ms 37,300 KB
testcase_46	AC	99 ms 38,300 KB
testcase_47	AC	81 ms 37,760 KB
testcase_48	AC	99 ms 38,380 KB
testcase_49	AC	61 ms 36,968 KB
testcase_50	AC	109 ms 38,172 KB
testcase_51	AC	105 ms 38,688 KB
testcase_52	AC	103 ms 38,376 KB
testcase_53	AC	95 ms 38,740 KB
testcase_54	AC	98 ms 38,348 KB
testcase_55	AC	91 ms 38,484 KB
testcase_56	AC	61 ms 36,912 KB
testcase_57	AC	94 ms 38,248 KB
testcase_58	AC	85 ms 38,376 KB
testcase_59	AC	58 ms 37,180 KB
testcase_60	AC	65 ms 37,192 KB
testcase_61	AC	95 ms 38,508 KB
testcase_62	AC	59 ms 37,012 KB
testcase_63	AC	199 ms 45,564 KB
testcase_64	AC	156 ms 40,164 KB
testcase_65	AC	178 ms 42,696 KB
testcase_66	AC	157 ms 41,556 KB
testcase_67	AC	137 ms 39,704 KB
testcase_68	AC	172 ms 42,172 KB
testcase_69	AC	184 ms 45,048 KB
testcase_70	AC	157 ms 40,688 KB
testcase_71	AC	143 ms 40,160 KB
testcase_72	AC	177 ms 45,276 KB
testcase_73	AC	150 ms 40,624 KB
testcase_74	AC	182 ms 45,164 KB
testcase_75	AC	165 ms 41,876 KB
testcase_76	AC	103 ms 38,696 KB
testcase_77	AC	163 ms 41,156 KB
testcase_78	AC	190 ms 45,608 KB
testcase_79	AC	194 ms 45,568 KB
testcase_80	AC	194 ms 45,356 KB
testcase_81	AC	196 ms 45,676 KB
testcase_82	AC	198 ms 45,556 KB
testcase_83	AC	813 ms 80,988 KB
testcase_84	AC	816 ms 74,000 KB
testcase_85	AC	565 ms 66,116 KB
testcase_86	AC	728 ms 71,688 KB
testcase_87	AC	747 ms 72,240 KB
testcase_88	AC	247 ms 49,012 KB
testcase_89	AC	854 ms 74,928 KB
testcase_90	AC	593 ms 66,524 KB
testcase_91	AC	515 ms 61,688 KB
testcase_92	AC	321 ms 53,016 KB
testcase_93	AC	725 ms 71,768 KB
testcase_94	AC	621 ms 67,520 KB
testcase_95	AC	627 ms 67,504 KB
testcase_96	AC	803 ms 72,900 KB
testcase_97	AC	464 ms 58,504 KB
testcase_98	AC	753 ms 76,044 KB
testcase_99	AC	499 ms 65,756 KB
testcase_100	AC	814 ms 76,032 KB
testcase_101	AC	304 ms 53,044 KB
testcase_102	AC	218 ms 46,568 KB
testcase_103	AC	312 ms 53,160 KB
testcase_104	AC	387 ms 56,888 KB
testcase_105	AC	718 ms 71,880 KB
testcase_106	AC	474 ms 58,244 KB
testcase_107	AC	753 ms 74,888 KB
testcase_108	AC	749 ms 74,160 KB
testcase_109	AC	686 ms 71,572 KB
testcase_110	AC	605 ms 67,412 KB
testcase_111	AC	707 ms 70,956 KB
testcase_112	AC	373 ms 56,808 KB
testcase_113	AC	588 ms 67,268 KB
testcase_114	AC	439 ms 58,208 KB
testcase_115	AC	232 ms 49,716 KB
testcase_116	AC	470 ms 61,996 KB
testcase_117	AC	362 ms 56,180 KB
testcase_118	AC	882 ms 73,640 KB
testcase_119	AC	518 ms 65,640 KB
testcase_120	AC	728 ms 74,132 KB
testcase_121	AC	310 ms 53,352 KB
testcase_122	AC	457 ms 61,732 KB
testcase_123	AC	58 ms 36,820 KB
testcase_124	AC	1,223 ms 101,976 KB
testcase_125	AC	973 ms 111,632 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import java.io.*;
import java.util.*;
import java.util.stream.*;

public class Main {
    static ArrayList<HashMap<Integer, Integer>> graph = new ArrayList<>();
    static int[] parents;
    static int[] depths;
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner();
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            graph.add(new HashMap<>());
        }
        UnionFindTree uft = new UnionFindTree(n);
        int left = 0;
        int right = 0;
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            if (uft.same(a, b)) {
                left = a;
                right = b;
                ans.add(i);
            } else {
                uft.unite(a, b);
                graph.get(a).put(b, i);
                graph.get(b).put(a, i);
            }
        }
        parents = new int[n];
        depths = new int[n];
        setDepth(0, 0, 0);
        while (left != right) {
            if (depths[left] == depths[right]) {
                ans.add(graph.get(left).get(parents[left]));
                left = parents[left];
                ans.add(graph.get(right).get(parents[right]));
                right = parents[right];
            } else if (depths[left] < depths[right]){
                ans.add(graph.get(right).get(parents[right]));
                right = parents[right];
            } else {
                ans.add(graph.get(left).get(parents[left]));
                left = parents[left];
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(ans.size()).append("\n");
        for (int i = 0; i < ans.size(); i++) {
            if (i > 0) {
                sb.append(" ");
            }
            sb.append(ans.get(i) + 1);
        }
        System.out.println(sb);
    }
    
    static void setDepth(int idx, int p, int d) {
        depths[idx] = d;
        parents[idx] = p;
        for (int x : graph.get(idx).keySet()) {
            if (x != p) {
                setDepth(x, idx, d + 1);
            }
        }
    }
    
    static class UnionFindTree {
        int[] parents;
        
        public UnionFindTree(int size) {
            parents = new int[size];
            for (int i = 0; i < size; i++) {
                parents[i] = i;
            }
        }
        
        public int find(int x) {
            if (parents[x] == x) {
                return x;
            } else {
                return parents[x] = find(parents[x]);
            }
        }
        
        public boolean same(int x, int y) {
            return find(x) == find(y);
        }
        
        public void unite(int x, int y) {
            if (!same(x, y)) {
                parents[find(x)] = find(y);
            }
        }
    }
}

class Utilities {
    static String arrayToLineString(Object[] arr) {
        return Arrays.stream(arr).map(x -> x.toString()).collect(Collectors.joining("\n"));
    }
    
    static String arrayToLineString(int[] arr) {
        return String.join("\n", Arrays.stream(arr).mapToObj(String::valueOf).toArray(String[]::new));
    }
}
class Scanner {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer("");
    StringBuilder sb = new StringBuilder();
    
    public Scanner() throws Exception {
        
    }
    
    public int nextInt() throws Exception {
        return Integer.parseInt(next());
    }
    
    public long nextLong() throws Exception {
        return Long.parseLong(next());
    }
    
    public double nextDouble() throws Exception {
        return Double.parseDouble(next());
    }
    
    public int[] nextIntArray() throws Exception {
        return Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
    
    public String next() throws Exception {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }
    
}

yukicoder

結果

テストケース

ソースコード