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

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	tenten
提出日時	2022-08-16 11:25:15
言語	Java21 (openjdk 21)
結果	AC
実行時間	1,110 ms / 2,000 ms
コード長	3,581 bytes
コンパイル時間	2,828 ms
コンパイル使用メモリ	80,476 KB
実行使用メモリ	114,644 KB
最終ジャッジ日時	2024-04-14 06:13:15
合計ジャッジ時間	45,092 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	57 ms 50,312 KB
testcase_01	AC	59 ms 50,124 KB
testcase_02	AC	57 ms 50,336 KB
testcase_03	AC	57 ms 49,836 KB
testcase_04	AC	58 ms 50,000 KB
testcase_05	AC	59 ms 50,392 KB
testcase_06	AC	58 ms 50,020 KB
testcase_07	AC	58 ms 50,468 KB
testcase_08	AC	57 ms 50,032 KB
testcase_09	AC	57 ms 50,380 KB
testcase_10	AC	58 ms 50,452 KB
testcase_11	AC	60 ms 50,036 KB
testcase_12	AC	57 ms 50,348 KB
testcase_13	AC	59 ms 50,256 KB
testcase_14	AC	61 ms 50,380 KB
testcase_15	AC	61 ms 50,300 KB
testcase_16	AC	59 ms 50,272 KB
testcase_17	AC	58 ms 49,920 KB
testcase_18	AC	60 ms 50,376 KB
testcase_19	AC	64 ms 50,376 KB
testcase_20	AC	60 ms 50,152 KB
testcase_21	AC	57 ms 50,464 KB
testcase_22	AC	63 ms 49,892 KB
testcase_23	AC	61 ms 50,332 KB
testcase_24	AC	58 ms 50,112 KB
testcase_25	AC	58 ms 50,396 KB
testcase_26	AC	61 ms 50,372 KB
testcase_27	AC	57 ms 50,336 KB
testcase_28	AC	55 ms 50,404 KB
testcase_29	AC	54 ms 50,008 KB
testcase_30	AC	54 ms 50,436 KB
testcase_31	AC	57 ms 50,284 KB
testcase_32	AC	55 ms 50,244 KB
testcase_33	AC	55 ms 50,416 KB
testcase_34	AC	55 ms 50,464 KB
testcase_35	AC	58 ms 50,376 KB
testcase_36	AC	60 ms 50,316 KB
testcase_37	AC	62 ms 50,140 KB
testcase_38	AC	62 ms 50,180 KB
testcase_39	AC	58 ms 50,452 KB
testcase_40	AC	59 ms 50,096 KB
testcase_41	AC	58 ms 50,472 KB
testcase_42	AC	57 ms 50,392 KB
testcase_43	AC	101 ms 51,192 KB
testcase_44	AC	71 ms 51,056 KB
testcase_45	AC	78 ms 50,912 KB
testcase_46	AC	102 ms 51,248 KB
testcase_47	AC	88 ms 50,916 KB
testcase_48	AC	94 ms 51,060 KB
testcase_49	AC	60 ms 50,388 KB
testcase_50	AC	100 ms 51,552 KB
testcase_51	AC	93 ms 51,368 KB
testcase_52	AC	89 ms 51,372 KB
testcase_53	AC	100 ms 51,568 KB
testcase_54	AC	89 ms 51,348 KB
testcase_55	AC	86 ms 51,296 KB
testcase_56	AC	65 ms 50,408 KB
testcase_57	AC	97 ms 51,540 KB
testcase_58	AC	93 ms 51,036 KB
testcase_59	AC	61 ms 50,360 KB
testcase_60	AC	70 ms 50,756 KB
testcase_61	AC	91 ms 51,276 KB
testcase_62	AC	63 ms 50,016 KB
testcase_63	AC	197 ms 57,508 KB
testcase_64	AC	144 ms 52,280 KB
testcase_65	AC	169 ms 54,872 KB
testcase_66	AC	161 ms 54,400 KB
testcase_67	AC	119 ms 52,200 KB
testcase_68	AC	157 ms 54,768 KB
testcase_69	AC	172 ms 55,560 KB
testcase_70	AC	142 ms 52,288 KB
testcase_71	AC	139 ms 52,224 KB
testcase_72	AC	173 ms 55,484 KB
testcase_73	AC	144 ms 52,308 KB
testcase_74	AC	167 ms 55,456 KB
testcase_75	AC	151 ms 54,536 KB
testcase_76	AC	108 ms 51,824 KB
testcase_77	AC	162 ms 54,260 KB
testcase_78	AC	187 ms 55,368 KB
testcase_79	AC	196 ms 55,616 KB
testcase_80	AC	185 ms 55,500 KB
testcase_81	AC	197 ms 55,436 KB
testcase_82	AC	177 ms 55,736 KB
testcase_83	AC	779 ms 85,972 KB
testcase_84	AC	762 ms 85,588 KB
testcase_85	AC	516 ms 75,740 KB
testcase_86	AC	702 ms 81,332 KB
testcase_87	AC	735 ms 81,744 KB
testcase_88	AC	228 ms 59,092 KB
testcase_89	AC	762 ms 85,780 KB
testcase_90	AC	567 ms 76,304 KB
testcase_91	AC	477 ms 72,644 KB
testcase_92	AC	286 ms 64,812 KB
testcase_93	AC	705 ms 81,764 KB
testcase_94	AC	592 ms 77,764 KB
testcase_95	AC	576 ms 77,696 KB
testcase_96	AC	754 ms 82,340 KB
testcase_97	AC	437 ms 67,552 KB
testcase_98	AC	771 ms 82,912 KB
testcase_99	AC	506 ms 75,848 KB
testcase_100	AC	742 ms 86,248 KB
testcase_101	AC	278 ms 64,828 KB
testcase_102	AC	234 ms 57,528 KB
testcase_103	AC	318 ms 64,868 KB
testcase_104	AC	387 ms 65,476 KB
testcase_105	AC	699 ms 81,724 KB
testcase_106	AC	461 ms 68,020 KB
testcase_107	AC	769 ms 85,768 KB
testcase_108	AC	744 ms 85,724 KB
testcase_109	AC	683 ms 81,244 KB
testcase_110	AC	568 ms 77,652 KB
testcase_111	AC	652 ms 80,968 KB
testcase_112	AC	348 ms 65,984 KB
testcase_113	AC	556 ms 77,732 KB
testcase_114	AC	418 ms 67,816 KB
testcase_115	AC	224 ms 59,328 KB
testcase_116	AC	460 ms 72,760 KB
testcase_117	AC	345 ms 65,796 KB
testcase_118	AC	741 ms 82,304 KB
testcase_119	AC	516 ms 75,572 KB
testcase_120	AC	734 ms 81,952 KB
testcase_121	AC	311 ms 64,856 KB
testcase_122	AC	473 ms 72,800 KB
testcase_123	AC	57 ms 50,228 KB
testcase_124	AC	1,110 ms 111,020 KB
testcase_125	AC	1,080 ms 114,644 KB

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

ソースコード

raw source code

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

public class Main {
    static ArrayList<HashMap<Integer, Integer>> graph = new ArrayList<>();
    static int[] depths;
    static int[] parents;
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner();
        int n = sc.nextInt();
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new HashMap<>());
        }
        UnionFindTree uft = new UnionFindTree(n);
        int orgA = 0;
        int orgB = 0;
        for (int i = 1; i <= n; i++) {
            int left = sc.nextInt() - 1;
            int right = sc.nextInt() - 1;
            if (uft.same(left, right)) {
                ans.add(i);
                orgA = left;
                orgB = right;
            } else {
                uft.unite(left, right);
                graph.get(left).put(right, i);
                graph.get(right).put(left, i);
            }
        }
        depths = new int[n];
        parents = new int[n];
        setDepth(0, 0, 0);
        setAns(orgA, orgB, ans);
        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));
        }
        System.out.println(sb);
    }
    
    static void setAns(int left, int right, ArrayList<Integer> ans) {
        if (depths[left] < depths[right]) {
            setAns(right, left, ans);
            return;
        }
        while (depths[left] > depths[right]) {
            ans.add(graph.get(left).get(parents[left]));
            left = parents[left];
        }
        while (left != right) {
            ans.add(graph.get(left).get(parents[left]));
            left = parents[left];
            ans.add(graph.get(right).get(parents[right]));
            right = parents[right];
        }
    }
    
    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) {
                continue;
            }
            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 (x == parents[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) {
            parents[find(x)] = find(y);
        }
    }
}

class Scanner {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer("");
    
    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 String next() throws Exception {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }
}

yukicoder

結果

テストケース

ソースコード