結果
問題 | No.1477 Lamps on Graph |
ユーザー | ks2m |
提出日時 | 2021-04-16 22:11:52 |
言語 | Java19 (openjdk 21) |
結果 |
AC
|
実行時間 | 967 ms / 2,000 ms |
コード長 | 1,676 bytes |
コンパイル時間 | 3,027 ms |
コンパイル使用メモリ | 81,804 KB |
実行使用メモリ | 90,096 KB |
最終ジャッジ日時 | 2023-09-16 00:57:11 |
合計ジャッジ時間 | 23,358 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 51 ms
50,256 KB |
testcase_01 | AC | 52 ms
50,264 KB |
testcase_02 | AC | 54 ms
50,228 KB |
testcase_03 | AC | 51 ms
50,336 KB |
testcase_04 | AC | 53 ms
50,220 KB |
testcase_05 | AC | 53 ms
50,352 KB |
testcase_06 | AC | 54 ms
50,344 KB |
testcase_07 | AC | 53 ms
50,672 KB |
testcase_08 | AC | 52 ms
50,348 KB |
testcase_09 | AC | 53 ms
50,544 KB |
testcase_10 | AC | 52 ms
50,256 KB |
testcase_11 | AC | 53 ms
50,504 KB |
testcase_12 | AC | 597 ms
68,768 KB |
testcase_13 | AC | 551 ms
68,568 KB |
testcase_14 | AC | 693 ms
68,668 KB |
testcase_15 | AC | 398 ms
61,356 KB |
testcase_16 | AC | 339 ms
61,708 KB |
testcase_17 | AC | 330 ms
61,284 KB |
testcase_18 | AC | 678 ms
75,380 KB |
testcase_19 | AC | 537 ms
68,064 KB |
testcase_20 | AC | 290 ms
61,312 KB |
testcase_21 | AC | 546 ms
67,720 KB |
testcase_22 | AC | 237 ms
56,872 KB |
testcase_23 | AC | 490 ms
63,636 KB |
testcase_24 | AC | 791 ms
75,676 KB |
testcase_25 | AC | 385 ms
60,900 KB |
testcase_26 | AC | 705 ms
70,916 KB |
testcase_27 | AC | 407 ms
63,236 KB |
testcase_28 | AC | 488 ms
68,020 KB |
testcase_29 | AC | 461 ms
65,400 KB |
testcase_30 | AC | 396 ms
63,796 KB |
testcase_31 | AC | 339 ms
61,504 KB |
testcase_32 | AC | 909 ms
87,328 KB |
testcase_33 | AC | 843 ms
81,752 KB |
testcase_34 | AC | 696 ms
90,096 KB |
testcase_35 | AC | 967 ms
79,876 KB |
testcase_36 | AC | 948 ms
81,208 KB |
testcase_37 | AC | 844 ms
77,716 KB |
testcase_38 | AC | 928 ms
79,252 KB |
testcase_39 | AC | 886 ms
81,328 KB |
ソースコード
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] sa = br.readLine().split(" "); int n = Integer.parseInt(sa[0]); int m = Integer.parseInt(sa[1]); sa = br.readLine().split(" "); Obj[] arr = new Obj[n]; PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o1.a - o2.a); for (int i = 0; i < n; i++) { Obj o = new Obj(); o.i = i; o.a = Integer.parseInt(sa[i]); que.add(o); arr[i] = o; } List<List<Integer>> list = new ArrayList<>(n); for (int i = 0; i < n; i++) { list.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { sa = br.readLine().split(" "); int u = Integer.parseInt(sa[0]) - 1; int v = Integer.parseInt(sa[1]) - 1; list.get(u).add(v); list.get(v).add(u); } int k = Integer.parseInt(br.readLine()); boolean[] p = new boolean[n]; sa = br.readLine().split(" "); for (int i = 0; i < k; i++) { int b = Integer.parseInt(sa[i]) - 1; p[b] = true; } br.close(); List<Integer> ans = new ArrayList<>(); while (!que.isEmpty()) { Obj o = que.poll(); if (!p[o.i]) { continue; } ans.add(o.i + 1); p[o.i] = false; for (int i : list.get(o.i)) { if (arr[i].a > o.a) { p[i] = !p[i]; } } } PrintWriter pw = new PrintWriter(System.out); pw.println(ans.size()); for (int i : ans) { pw.println(i); } pw.flush(); } static class Obj { int i, a; } }