結果
問題 | No.1647 Travel in Mitaru city 2 |
ユーザー |
![]() |
提出日時 | 2021-08-13 22:52:17 |
言語 | Java (openjdk 23) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,654 bytes |
コンパイル時間 | 2,196 ms |
コンパイル使用メモリ | 78,652 KB |
実行使用メモリ | 103,780 KB |
最終ジャッジ日時 | 2024-10-03 21:34:35 |
合計ジャッジ時間 | 40,018 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 WA * 22 TLE * 1 |
ソースコード
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 (int i = 0; i < n; i++) {if (dfs(arr[i].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)) {if (o != p) {if (his.contains(o)) {System.out.println(his.size());StringBuilder sb = new StringBuilder();for (Hen o2 : his) {sb.append(o2.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;}}