結果

問題 No.1605 Matrix Shape
ユーザー ks2mks2m
提出日時 2021-07-16 22:18:30
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 2,026 bytes
コンパイル時間 1,933 ms
コンパイル使用メモリ 78,504 KB
実行使用メモリ 89,856 KB
最終ジャッジ日時 2024-07-06 09:40:38
合計ジャッジ時間 8,514 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 17 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Main {
static int n;
static List<List<Hen>> list;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
int m = 200000;
list = new ArrayList<>(m);
for (int i = 0; i < m; i++) {
list.add(new ArrayList<>());
}
int[] in = new int[m];
int[] out = new int[m];
for (int i = 0; i < n; i++) {
String[] sa = br.readLine().split(" ");
Hen h = new Hen();
h.a = Integer.parseInt(sa[0]) - 1;
h.b = Integer.parseInt(sa[1]) - 1;
list.get(h.a).add(h);
out[h.a]++;
in[h.b]++;
}
br.close();
int s = -1;
int t = -1;
boolean even = false;
for (int i = 0; i < m; i++) {
if (in[i] != out[i]) {
if (Math.abs(in[i] - out[i]) > 1) {
System.out.println(0);
return;
}
if (in[i] + 1 == out[i]) {
if (s == -1) {
s = i;
} else {
System.out.println(0);
return;
}
} else {
if (t == -1) {
t = i;
} else {
System.out.println(0);
return;
}
}
}
}
if (s == -1) {
for (int i = 0; i < m; i++) {
if (out[i] > 0) {
s = i;
break;
}
}
even = true;
}
boolean res = dfs(s, new ArrayList<>(n));
if (res) {
if (even) {
int ans = 0;
for (int i = 0; i < m; i++) {
if (!list.get(i).isEmpty()) {
ans++;
}
}
System.out.println(ans);
} else {
System.out.println(1);
}
} else {
System.out.println(0);
}
}
static boolean dfs(int x, List<Hen> his) {
if (his.size() == n) {
return true;
}
for (Hen h : list.get(x)) {
if (!h.used) {
h.used = true;
his.add(h);
boolean res = dfs(h.b, his);
if (res) {
return true;
}
his.remove(his.size() - 1);
h.used = false;
}
}
return false;
}
static class Hen {
int a, b;
boolean used;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0