結果
問題 | No.2674 k-Walk on Bipartite |
ユーザー |
![]() |
提出日時 | 2024-03-15 23:32:40 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 995 ms / 2,000 ms |
コード長 | 3,157 bytes |
コンパイル時間 | 2,292 ms |
コンパイル使用メモリ | 78,484 KB |
実行使用メモリ | 85,720 KB |
最終ジャッジ日時 | 2024-09-30 03:06:53 |
合計ジャッジ時間 | 16,433 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Queue;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(" ");int s = Integer.parseInt(sa[0]) - 1;int t = Integer.parseInt(sa[1]) - 1;int k = Integer.parseInt(sa[2]);Node2[] arr = new Node2[n];for (int i = 0; i < n; i++) {Node2 o = new Node2();arr[i] = o;}UnionFind uf = new UnionFind(n);for (int i = 0; i < m; i++) {sa = br.readLine().split(" ");int a = Integer.parseInt(sa[0]) - 1;int b = Integer.parseInt(sa[1]) - 1;arr[a].nexts.add(b);arr[b].nexts.add(a);uf.union(a, b);}br.close();Queue<Integer> que = new ArrayDeque<>();for (int i = 0; i < n; i++) {if (arr[i].grp == 0) {que.add(i);arr[i].grp = 1;while (!que.isEmpty()) {int cur = que.poll();for (int next : arr[cur].nexts) {if (arr[next].grp == 0) {que.add(next);arr[next].grp = 3 - arr[cur].grp;} else if (arr[next].grp == arr[cur].grp) {// 二部グラフではないthrow new RuntimeException();}}}}}if (uf.same(s, t)) {if ((arr[s].grp == arr[t].grp) ^ (k % 2 == 1)) {int[] d = new int[n];Arrays.fill(d, -1);d[s] = 0;que = new ArrayDeque<>();que.add(s);while (!que.isEmpty()) {int cur = que.poll();for (int next : arr[cur].nexts) {if (d[next] == -1) {que.add(next);d[next] = d[cur] + 1;}}}if (d[t] <= k) {if (n == 1) {System.out.println("No");} else {if (d[t] == 0 && arr[t].nexts.isEmpty()) {System.out.println("Unknown");} else {System.out.println("Yes");}}} else {System.out.println("Unknown");}} else {System.out.println("No");}} else {if (n == 2 && k % 2 == 0) {System.out.println("No");} else {System.out.println("Unknown");}}}static class Node2 {int grp;Integer target;List<Integer> nexts = new ArrayList<>();}static class UnionFind {int[] parent, size;int num = 0; // 連結成分の数UnionFind(int n) {parent = new int[n];size = new int[n];num = n;for (int i = 0; i < n; i++) {parent[i] = i;size[i] = 1;}}void union(int x, int y) {int px = find(x);int py = find(y);if (px != py) {parent[px] = py;size[py] += size[px];num--;}}int find(int x) {if (parent[x] == x) {return x;}parent[x] = find(parent[x]);return parent[x];}/*** xとyが同一連結成分か*/boolean same(int x, int y) {return find(x) == find(y);}/*** xを含む連結成分のサイズ*/int size(int x) {return size[find(x)];}}}