AtCoder Typical Contest 001

Submission #5403021

Source codeソースコード

import java.io.IOException;
import java.io.InputStream;
import java.util.*;
 
 
public class Main {
	
    public static void main(String[] args) {
    	FastScanner sc = new FastScanner();
    	
    	int n = sc.nextInt();
    	int q = sc.nextInt();
    	
    	UnionFindTree uf = new UnionFindTree(n);
    	
    	for(int i=0;i<q;i++){
    		
    		int p = sc.nextInt();
    		int a = sc.nextInt();
    		int b = sc.nextInt();
    		
    		
    		if(p==0){
    			uf.unite(a, b);
    		}
    		else{
    			if(uf.isEquivalent(a, b)){
    				System.out.println("Yes");
    			}
    			else{
    				System.out.println("No");
    			}
    		}
    	}
 
    }
    
}
 
class UnionFindTree {
	int[] par;
	int[] rank;
	int[] peers; //仲間の数
	
	public UnionFindTree(int n){
		par = new int[n];
		rank = new int[n];
		peers = new int[n];
		
		for(int i=0;i<n;i++){
			par[i] = i;
			peers[i] = 1;
		}
	}
	
	//木の根を求める
	int find(int x){
		if(par[x] == x){
			return x;
		}
		else{
			return par[x] = find(par[x]);
		}
	}
	
	//xとyの属する集合を併合
	void unite(int x, int y){
		int px = find(x);
		int py = find(y);
		
		if(px == py){
			return;
		}
		else if(rank[px] < rank[py]){
			peers[py] += peers[px];
			par[px] = py;
 
		}
		else{
			peers[px] += peers[py];
			par[py] = px;
			if(rank[px]==rank[py]){
				rank[px]++;
			}
		}
		
	}
	
	//xとyが同じ集合に属するか
	boolean isEquivalent(int x, int y){
		return find(x) == find(y);
	}
	
	//xの仲間の数を求める
	int peersnum(int x){
		return peers[find(x)];
	}
}
 
 
class FastScanner {
    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();}
    public 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();
    }
    public 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();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}

Submission

Task問題 B - Union Find
User nameユーザ名 warachia
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 AC
Score得点 100
Source lengthソースコード長 3809 Byte
File nameファイル名
Exec time実行時間 1071 ms
Memory usageメモリ使用量 53320 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_sample_01.txt
All 100 / 100 00_sample_01.txt,subtask_01_01.txt,subtask_01_02.txt,subtask_01_03.txt,subtask_01_04.txt,subtask_01_05.txt,subtask_01_06.txt,subtask_01_07.txt,subtask_01_08.txt,subtask_01_09.txt,subtask_01_10.txt,subtask_01_11.txt,subtask_01_12.txt,subtask_01_13.txt,subtask_01_14.txt,subtask_01_15.txt,subtask_01_16.txt,subtask_01_17.txt,subtask_01_18.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample_01.txt AC 69 ms 17876 KB
subtask_01_01.txt AC 679 ms 34236 KB
subtask_01_02.txt AC 71 ms 18644 KB
subtask_01_03.txt AC 983 ms 40128 KB
subtask_01_04.txt AC 1051 ms 51252 KB
subtask_01_05.txt AC 193 ms 22628 KB
subtask_01_06.txt AC 192 ms 22036 KB
subtask_01_07.txt AC 1005 ms 39244 KB
subtask_01_08.txt AC 1071 ms 52508 KB
subtask_01_09.txt AC 72 ms 21076 KB
subtask_01_10.txt AC 72 ms 19412 KB
subtask_01_11.txt AC 999 ms 38480 KB
subtask_01_12.txt AC 1063 ms 53288 KB
subtask_01_13.txt AC 823 ms 41040 KB
subtask_01_14.txt AC 100 ms 21204 KB
subtask_01_15.txt AC 992 ms 39196 KB
subtask_01_16.txt AC 1046 ms 53320 KB
subtask_01_17.txt AC 681 ms 43632 KB
subtask_01_18.txt AC 673 ms 42928 KB