結果
問題 | No.2316 Freight Train |
ユーザー |
![]() |
提出日時 | 2023-05-26 21:27:27 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 707 ms / 2,000 ms |
コード長 | 1,607 bytes |
コンパイル時間 | 3,862 ms |
コンパイル使用メモリ | 76,444 KB |
実行使用メモリ | 77,584 KB |
最終ジャッジ日時 | 2024-12-25 04:51:57 |
合計ジャッジ時間 | 20,009 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.PrintWriter;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 q = Integer.parseInt(sa[1]);sa = br.readLine().split(" ");UnionFind uf = new UnionFind(n);for (int i = 0; i < n; i++) {int p = Integer.parseInt(sa[i]) - 1;if (p != -2) {uf.union(p, i);}}PrintWriter pw = new PrintWriter(System.out);for (int i = 0; i < q; i++) {sa = br.readLine().split(" ");int a = Integer.parseInt(sa[0]) - 1;int b = Integer.parseInt(sa[1]) - 1;if (uf.same(a, b)) {pw.println("Yes");} else {pw.println("No");}}pw.flush();br.close();}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)];}}}