結果
問題 | No.2316 Freight Train |
ユーザー |
|
提出日時 | 2023-05-26 22:42:50 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 389 ms / 2,000 ms |
コード長 | 6,910 bytes |
コンパイル時間 | 2,485 ms |
コンパイル使用メモリ | 80,280 KB |
実行使用メモリ | 51,380 KB |
最終ジャッジ日時 | 2024-12-25 09:04:02 |
合計ジャッジ時間 | 13,075 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
import java.util.*;import java.io.*;class Main{void solve(PrintWriter out, In in) {int n = in.nextInt() , Q = in.nextInt();int [] par = in.IntArray(n);DSU dsu = new DSU(n);for(int i = 0 ; i < n ; i ++ ) {if(par[i] == -1) continue;dsu.unite(i,par[i]-1);}while(Q-->0) {int a = in.nextInt() , b = in.nextInt();a--;b--;out.println(dsu.same(a,b)?"Yes":"No");}}/* Library */class DSU {private int[] rank;private int [] parent;private int [] size;DSU(int n) {this.parent = new int[n];this.rank = new int[n];this.size = new int[n];for (int i = 0 ; i < n; i ++ ) {parent[i] = i;rank[i] = 0;size[i] = 1;}}int groups() {int count = 0;for(int i = 0;i < parent.length ; i ++ ) {if(i == find(i)) {count++;}}return count;}int size(int x){return size[find(x)];}int find(int x) {if (x == parent[x]) {return x;} else {parent[x] = find(parent[x]);return parent[x];}}boolean same(int x, int y) {return find(x) == find(y);}void unite(int x, int y) {int xRoot = find(x);int yRoot = find(y);if (xRoot == yRoot) {return;}if (rank[xRoot] > rank[yRoot]) {parent[yRoot] = xRoot;} else if (rank[xRoot] < rank[yRoot]) {parent[xRoot] = yRoot;} else {parent[xRoot] = yRoot;rank[xRoot]++;size[yRoot] += size[xRoot];}}}/* ------- */public static void main(String[] args) {PrintWriter out = new PrintWriter(System.out);In in = new In();new Main().solve(out,in);out.flush();}/* Const */final long MOD7 = 1000000007; final long MOD9 = 998244353 ;final int [] X4 = {0,1,0,-1}; final int [] Y4 = {-1,0,1,0};final int [] X8 = {-1,-1,0,1,1,1,0,-1}; final int [] Y8 = {0,1,1,1,0,-1,-1,-1};final int Inf = (int)1e9; final long Lnf = (long)1e18;final String yes = "Yes"; final String no = "No";/* ----- */}/* Class *//* ----- */class Pair{private int first ;private int second;Pair(int first,int second) {this.first = first;this.second = second;}int first() { return this.first ; }int second() { return this.second; }@Overridepublic String toString(){ return first()+" = "+second(); }}class PairII {private int first ;private int second ;private int third;PairII(int first, int second, int third) {this.first = first;this.second = second;this.third = third;}int first() { return this.first ; }int second() { return this.second; }int third() { return this.third ; }@Overridepublic String toString(){ return first()+" = "+second()+" = "+third() ; }}class In{private final InputStream in = System.in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int buflen = 0;private boolean hasNextByte() {if (ptr < buflen) {return true;}else{ptr = 0;try {buflen = in.read(buffer);} catch (IOException e) {e.printStackTrace();}if (buflen <= 0) {return false;}}return true;}private int readByte() {if (hasNextByte()) return buffer[ptr++]; else return -1;}private static boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}public boolean hasNext() {while(hasNextByte() && !isPrintableChar(buffer[ptr])) {ptr++;}return hasNextByte();}String next() {if (!hasNext()) throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while(isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}long nextLong() {if (!hasNext()) throw new NoSuchElementException();long n = 0;boolean minus = false;int b = readByte();if (b == '-') {minus = true;b = readByte();}if (b < '0' || '9' < b) {throw new NumberFormatException();}while(true){if ('0' <= b && b <= '9') {n *= 10;n += b - '0';}else if(b == -1 || !isPrintableChar(b)){return minus ? -n : n;}else{throw new NumberFormatException();}b = readByte();}}int nextInt() {long nl = nextLong();if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();return (int) nl;}double nextDouble() {return Double.parseDouble(next());}int [] IntArray(int n) {final int [] Array = new int [n];for(int i = 0 ; i < n ; i ++ ) {Array[i] = nextInt();}return Array;}int [][] IntArray(int n , int m) {final int [][] Array = new int [n][m];for(int i = 0 ; i < n ; i ++ ) {Array[i] = IntArray(m);}return Array;}long [] LongArray(int n) {final long [] Array = new long [n];for(int i = 0 ; i < n ; i ++ ) {Array[i] = nextLong();}return Array;}long [][] LongArray(int n , int m) {final long [][] Array = new long [n][m];for(int i = 0 ; i < n ; i ++ ) {Array[i] = LongArray(m);}return Array;}String [] StringArray(int n) {final String [] Array = new String [n];for(int i = 0 ; i < n ; i ++ ) {Array[i] = next();}return Array;}char [] CharArray(int n) {final char [] Array = new char[n];for(int i = 0 ; i < n ; i ++ ) {Array[i] = next().charAt(0);}return Array;}char [][] CharArray(int n , int m) {final char [][] Array = new char [n][m];for(int i = 0 ; i < n ; i ++ ) {Array[i] = next().toCharArray();}return Array;}}