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

• 問題: No.1254 補強への架け橋
• ユーザー: tenten
• 提出日時: 2022-08-16 11:25:15
• 言語: Java21 (openjdk 21)
• 結果: AC
• 実行時間: 974 ms / 2,000 ms
• コード長: 3,581 bytes
• コンパイル時間: 2,396 ms
• コンパイル使用メモリ: 80,120 KB
• 実行使用メモリ: 108,004 KB
• 最終ジャッジ日時: 2024-10-03 03:29:30
• 合計ジャッジ時間: 41,236 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	54 ms; 37,088 KB
testcase_01	AC	54 ms; 36,988 KB
testcase_02	AC	55 ms; 36,788 KB
testcase_03	AC	53 ms; 37,192 KB
testcase_04	AC	54 ms; 36,896 KB
testcase_05	AC	54 ms; 37,064 KB
testcase_06	AC	55 ms; 36,944 KB
testcase_07	AC	54 ms; 36,724 KB
testcase_08	AC	55 ms; 36,900 KB
testcase_09	AC	54 ms; 37,232 KB
testcase_10	AC	54 ms; 37,088 KB
testcase_11	AC	55 ms; 36,832 KB
testcase_12	AC	55 ms; 36,932 KB
testcase_13	AC	56 ms; 37,120 KB
testcase_14	AC	56 ms; 37,216 KB
testcase_15	AC	54 ms; 36,876 KB
testcase_16	AC	55 ms; 37,104 KB
testcase_17	AC	54 ms; 36,836 KB
testcase_18	AC	53 ms; 36,756 KB
testcase_19	AC	54 ms; 37,048 KB
testcase_20	AC	55 ms; 37,116 KB
testcase_21	AC	55 ms; 37,072 KB
testcase_22	AC	55 ms; 37,100 KB
testcase_23	AC	55 ms; 36,960 KB
testcase_24	AC	56 ms; 37,228 KB
testcase_25	AC	54 ms; 37,052 KB
testcase_26	AC	55 ms; 37,116 KB
testcase_27	AC	59 ms; 37,228 KB
testcase_28	AC	56 ms; 37,104 KB
testcase_29	AC	55 ms; 37,148 KB
testcase_30	AC	54 ms; 36,584 KB
testcase_31	AC	55 ms; 37,024 KB
testcase_32	AC	55 ms; 36,792 KB
testcase_33	AC	56 ms; 37,216 KB
testcase_34	AC	56 ms; 37,232 KB
testcase_35	AC	56 ms; 37,072 KB
testcase_36	AC	56 ms; 37,228 KB
testcase_37	AC	56 ms; 37,228 KB
testcase_38	AC	56 ms; 37,072 KB
testcase_39	AC	55 ms; 37,044 KB
testcase_40	AC	55 ms; 36,804 KB
testcase_41	AC	55 ms; 36,580 KB
testcase_42	AC	54 ms; 37,080 KB
testcase_43	AC	85 ms; 38,112 KB
testcase_44	AC	67 ms; 37,704 KB
testcase_45	AC	64 ms; 37,064 KB
testcase_46	AC	93 ms; 38,604 KB
testcase_47	AC	83 ms; 38,356 KB
testcase_48	AC	91 ms; 38,252 KB
testcase_49	AC	57 ms; 37,004 KB
testcase_50	AC	87 ms; 38,412 KB
testcase_51	AC	97 ms; 38,636 KB
testcase_52	AC	93 ms; 38,564 KB
testcase_53	AC	92 ms; 38,336 KB
testcase_54	AC	91 ms; 38,468 KB
testcase_55	AC	88 ms; 38,636 KB
testcase_56	AC	58 ms; 36,720 KB
testcase_57	AC	86 ms; 38,308 KB
testcase_58	AC	81 ms; 38,156 KB
testcase_59	AC	57 ms; 37,060 KB
testcase_60	AC	64 ms; 37,248 KB
testcase_61	AC	95 ms; 38,428 KB
testcase_62	AC	59 ms; 37,196 KB
testcase_63	AC	170 ms; 45,264 KB
testcase_64	AC	136 ms; 40,312 KB
testcase_65	AC	159 ms; 42,720 KB
testcase_66	AC	148 ms; 41,836 KB
testcase_67	AC	126 ms; 39,760 KB
testcase_68	AC	153 ms; 41,840 KB
testcase_69	AC	156 ms; 45,068 KB
testcase_70	AC	137 ms; 40,528 KB
testcase_71	AC	134 ms; 40,416 KB
testcase_72	AC	166 ms; 45,284 KB
testcase_73	AC	139 ms; 40,652 KB
testcase_74	AC	166 ms; 45,004 KB
testcase_75	AC	147 ms; 41,780 KB
testcase_76	AC	100 ms; 38,756 KB
testcase_77	AC	147 ms; 41,568 KB
testcase_78	AC	166 ms; 45,524 KB
testcase_79	AC	173 ms; 45,700 KB
testcase_80	AC	164 ms; 45,324 KB
testcase_81	AC	173 ms; 45,324 KB
testcase_82	AC	174 ms; 45,556 KB
testcase_83	AC	714 ms; 75,044 KB
testcase_84	AC	694 ms; 74,696 KB
testcase_85	AC	476 ms; 66,272 KB
testcase_86	AC	652 ms; 71,432 KB
testcase_87	AC	686 ms; 71,936 KB
testcase_88	AC	211 ms; 49,372 KB
testcase_89	AC	698 ms; 75,188 KB
testcase_90	AC	494 ms; 66,536 KB
testcase_91	AC	427 ms; 61,640 KB
testcase_92	AC	276 ms; 52,780 KB
testcase_93	AC	645 ms; 71,904 KB
testcase_94	AC	528 ms; 67,388 KB
testcase_95	AC	530 ms; 67,432 KB
testcase_96	AC	664 ms; 73,068 KB
testcase_97	AC	395 ms; 57,960 KB
testcase_98	AC	696 ms; 77,680 KB
testcase_99	AC	479 ms; 65,892 KB
testcase_100	AC	714 ms; 80,472 KB
testcase_101	AC	258 ms; 52,880 KB
testcase_102	AC	195 ms; 46,748 KB
testcase_103	AC	280 ms; 53,020 KB
testcase_104	AC	345 ms; 55,248 KB
testcase_105	AC	654 ms; 71,636 KB
testcase_106	AC	409 ms; 58,444 KB
testcase_107	AC	696 ms; 75,020 KB
testcase_108	AC	686 ms; 74,968 KB
testcase_109	AC	626 ms; 71,772 KB
testcase_110	AC	525 ms; 67,404 KB
testcase_111	AC	618 ms; 71,200 KB
testcase_112	AC	319 ms; 55,408 KB
testcase_113	AC	519 ms; 67,348 KB
testcase_114	AC	399 ms; 57,996 KB
testcase_115	AC	217 ms; 49,396 KB
testcase_116	AC	435 ms; 61,688 KB
testcase_117	AC	315 ms; 55,644 KB
testcase_118	AC	664 ms; 72,776 KB
testcase_119	AC	464 ms; 65,592 KB
testcase_120	AC	656 ms; 71,964 KB
testcase_121	AC	292 ms; 53,192 KB
testcase_122	AC	434 ms; 61,684 KB
testcase_123	AC	53 ms; 37,148 KB
testcase_124	AC	974 ms; 96,444 KB
testcase_125	AC	933 ms; 108,004 KB

ソースコード

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();
    }
}