結果
問題 | No.1647 Travel in Mitaru city 2 |
ユーザー |
![]() |
提出日時 | 2021-08-13 22:58:15 |
言語 | Java (openjdk 23) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,879 bytes |
コンパイル時間 | 2,525 ms |
コンパイル使用メモリ | 78,628 KB |
実行使用メモリ | 92,792 KB |
最終ジャッジ日時 | 2024-10-03 22:05:10 |
合計ジャッジ時間 | 44,976 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 WA * 7 |
ソースコード
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.LinkedHashSet;import java.util.List;public class Main {static int h, w, n, hw;static List<List<Hen>> list;public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] sa = br.readLine().split(" ");h = Integer.parseInt(sa[0]);w = Integer.parseInt(sa[1]);n = Integer.parseInt(sa[2]);hw = h + w;list = new ArrayList<>(hw);for (int i = 0; i < hw; i++) {list.add(new ArrayList<>());}Hen[] arr = new Hen[n];for (int i = 0; i < n; i++) {sa = br.readLine().split(" ");Hen o = new Hen();o.i = i;o.x = Integer.parseInt(sa[0]) - 1;o.y = Integer.parseInt(sa[1]) - 1 + h;list.get(o.x).add(o);list.get(o.y).add(o);arr[i] = o;}br.close();for (Hen o : arr) {if (!o.used) {if (dfs(o.x, null, new LinkedHashSet<>())) {return;}}}System.out.println(-1);}static boolean dfs(int x, Hen p, LinkedHashSet<Hen> his) {for (Hen o : list.get(x)) {o.used = true;if (o != p) {if (his.contains(o)) {Hen[] arr = his.toArray(new Hen[0]);int s = 0;for (int i = 0; i < arr.length; i++) {if (arr[i] == o) {s = i;break;}}System.out.println(arr.length - s);StringBuilder sb = new StringBuilder();for (int i = s; i < arr.length; i++) {sb.append(arr[i].i + 1).append(' ');}sb.deleteCharAt(sb.length() - 1);System.out.println(sb.toString());return true;}his.add(o);int nx = o.x;if (nx == x) {nx = o.y;}if (dfs(nx, o, his)) {return true;}his.remove(o);}}return false;}static class Hen {int x, y, i;boolean used;}}