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

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	tenten
提出日時	2020-11-20 08:18:58
言語	Java21 (openjdk 21)
結果	AC
実行時間	1,593 ms / 2,000 ms
コード長	1,621 bytes
コンパイル時間	4,816 ms
コンパイル使用メモリ	75,940 KB
実行使用メモリ	85,828 KB
最終ジャッジ日時	2023-09-30 18:18:29
合計ジャッジ時間	66,540 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	130 ms 39,164 KB
testcase_01	AC	122 ms 39,256 KB
testcase_02	AC	120 ms 39,392 KB
testcase_03	AC	120 ms 39,260 KB
testcase_04	AC	131 ms 39,772 KB
testcase_05	AC	120 ms 39,456 KB
testcase_06	AC	120 ms 39,212 KB
testcase_07	AC	121 ms 39,240 KB
testcase_08	AC	121 ms 39,772 KB
testcase_09	AC	122 ms 39,624 KB
testcase_10	AC	120 ms 39,204 KB
testcase_11	AC	121 ms 39,344 KB
testcase_12	AC	120 ms 39,600 KB
testcase_13	AC	135 ms 40,072 KB
testcase_14	AC	139 ms 39,816 KB
testcase_15	AC	131 ms 39,720 KB
testcase_16	AC	128 ms 39,296 KB
testcase_17	AC	121 ms 39,428 KB
testcase_18	AC	120 ms 39,788 KB
testcase_19	AC	129 ms 39,884 KB
testcase_20	AC	135 ms 40,192 KB
testcase_21	AC	124 ms 39,464 KB
testcase_22	AC	132 ms 39,768 KB
testcase_23	AC	132 ms 39,304 KB
testcase_24	AC	143 ms 39,944 KB
testcase_25	AC	130 ms 39,424 KB
testcase_26	AC	133 ms 40,140 KB
testcase_27	AC	130 ms 39,444 KB
testcase_28	AC	133 ms 39,596 KB
testcase_29	AC	131 ms 39,600 KB
testcase_30	AC	128 ms 39,924 KB
testcase_31	AC	136 ms 40,032 KB
testcase_32	AC	124 ms 39,292 KB
testcase_33	AC	135 ms 39,668 KB
testcase_34	AC	134 ms 39,876 KB
testcase_35	AC	136 ms 40,200 KB
testcase_36	AC	134 ms 39,860 KB
testcase_37	AC	135 ms 39,980 KB
testcase_38	AC	135 ms 39,616 KB
testcase_39	AC	131 ms 39,608 KB
testcase_40	AC	135 ms 39,552 KB
testcase_41	AC	131 ms 39,596 KB
testcase_42	AC	127 ms 39,988 KB
testcase_43	AC	206 ms 42,224 KB
testcase_44	AC	184 ms 40,144 KB
testcase_45	AC	180 ms 40,012 KB
testcase_46	AC	197 ms 41,308 KB
testcase_47	AC	188 ms 40,296 KB
testcase_48	AC	189 ms 41,432 KB
testcase_49	AC	139 ms 39,744 KB
testcase_50	AC	200 ms 41,760 KB
testcase_51	AC	196 ms 41,460 KB
testcase_52	AC	204 ms 41,668 KB
testcase_53	AC	207 ms 41,264 KB
testcase_54	AC	198 ms 41,512 KB
testcase_55	AC	198 ms 41,356 KB
testcase_56	AC	147 ms 40,076 KB
testcase_57	AC	188 ms 40,776 KB
testcase_58	AC	192 ms 41,516 KB
testcase_59	AC	140 ms 39,920 KB
testcase_60	AC	176 ms 40,484 KB
testcase_61	AC	199 ms 41,568 KB
testcase_62	AC	151 ms 40,072 KB
testcase_63	AC	342 ms 46,572 KB
testcase_64	AC	229 ms 44,436 KB
testcase_65	AC	280 ms 46,312 KB
testcase_66	AC	261 ms 45,348 KB
testcase_67	AC	224 ms 44,236 KB
testcase_68	AC	270 ms 45,380 KB
testcase_69	AC	310 ms 46,248 KB
testcase_70	AC	237 ms 44,576 KB
testcase_71	AC	227 ms 44,920 KB
testcase_72	AC	299 ms 46,392 KB
testcase_73	AC	232 ms 44,656 KB
testcase_74	AC	296 ms 46,048 KB
testcase_75	AC	267 ms 45,696 KB
testcase_76	AC	197 ms 42,072 KB
testcase_77	AC	255 ms 45,148 KB
testcase_78	AC	336 ms 46,380 KB
testcase_79	AC	325 ms 46,360 KB
testcase_80	AC	311 ms 46,304 KB
testcase_81	AC	327 ms 46,364 KB
testcase_82	AC	311 ms 46,412 KB
testcase_83	AC	1,032 ms 65,392 KB
testcase_84	AC	1,028 ms 72,040 KB
testcase_85	AC	775 ms 56,044 KB
testcase_86	AC	954 ms 62,792 KB
testcase_87	AC	979 ms 63,648 KB
testcase_88	AC	374 ms 47,288 KB
testcase_89	AC	1,060 ms 64,676 KB
testcase_90	AC	764 ms 57,620 KB
testcase_91	AC	689 ms 53,404 KB
testcase_92	AC	486 ms 48,868 KB
testcase_93	AC	937 ms 62,096 KB
testcase_94	AC	860 ms 57,756 KB
testcase_95	AC	877 ms 67,040 KB
testcase_96	AC	1,008 ms 63,836 KB
testcase_97	AC	646 ms 51,196 KB
testcase_98	AC	1,022 ms 63,736 KB
testcase_99	AC	755 ms 55,780 KB
testcase_100	AC	1,057 ms 64,988 KB
testcase_101	AC	465 ms 48,548 KB
testcase_102	AC	359 ms 47,088 KB
testcase_103	AC	492 ms 49,236 KB
testcase_104	AC	591 ms 50,204 KB
testcase_105	AC	933 ms 61,516 KB
testcase_106	AC	646 ms 52,212 KB
testcase_107	AC	1,073 ms 64,944 KB
testcase_108	AC	1,040 ms 64,180 KB
testcase_109	AC	913 ms 60,844 KB
testcase_110	AC	841 ms 57,984 KB
testcase_111	AC	894 ms 60,212 KB
testcase_112	AC	553 ms 49,976 KB
testcase_113	AC	844 ms 57,480 KB
testcase_114	AC	635 ms 52,400 KB
testcase_115	AC	387 ms 46,988 KB
testcase_116	AC	685 ms 54,092 KB
testcase_117	AC	540 ms 49,652 KB
testcase_118	AC	1,018 ms 63,612 KB
testcase_119	AC	754 ms 56,032 KB
testcase_120	AC	1,003 ms 63,864 KB
testcase_121	AC	537 ms 49,228 KB
testcase_122	AC	685 ms 53,928 KB
testcase_123	AC	125 ms 39,656 KB
testcase_124	AC	1,478 ms 80,092 KB
testcase_125	AC	1,593 ms 85,828 KB

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

ソースコード

raw source code

import java.util.*;

public class Main {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int[] ord;
    static int[] lowLink;
    static int count = 0;
    
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i = 0; i < n; i++) {
		    graph.add(new ArrayList<>());
		}
		int[] lefts = new int[n];
		int[] rights = new int[n];
		for (int i = 0; i < n; i++) {
		    int a = sc.nextInt() - 1;
		    int b = sc.nextInt() - 1;
		    graph.get(a).add(b);
		    graph.get(b).add(a);
		    lefts[i] = a;
		    rights[i] = b;
		}
		ord = new int[n];
		lowLink = new int[n];
		search(0, 0);
		ArrayList<Integer> ans = new ArrayList<>();
		for (int i = 0; i < n; i++) {
		    if ((ord[lefts[i]] < ord[rights[i]] && ord[lefts[i]] >= lowLink[rights[i]]) ||
		       (ord[lefts[i]] > ord[rights[i]] && lowLink[lefts[i]] <= ord[rights[i]])) {
		        ans.add(i + 1);
		    }
		}
		StringBuilder sb = new StringBuilder();
		Collections.sort(ans);
		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 int search(int idx, int from) {
       if (ord[idx] > 0) {
           return ord[idx];
       }
       count++;
       ord[idx] = count;
       lowLink[idx] = count;
       for (int x : graph.get(idx)) {
           if (x == from) {
               continue;
           }
           lowLink[idx] = Math.min(lowLink[idx], search(x, idx));
       }
       return lowLink[idx];
   }
}

yukicoder

結果

テストケース

ソースコード