AtCoder Typical Contest 001

Submission #5359923

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();
    	
    	int[] p = new int[q];
    	int[] a = new int[q];
    	int[] b = new int[q];
    	
    	for(int i=0;i<q;i++){
    		p[i] = sc.nextInt();
    		a[i] = sc.nextInt();
    		b[i] = sc.nextInt();
    	}
    	
    	UnionFindTree uf = new UnionFindTree(n);
    	
    	for(int i=0;i<q;i++){
    		
    		if(p[i]==0){
    			uf.unite(a[i], b[i]);
    		}
    		else{
    			if(uf.isEquivalent(a[i], b[i])){
    				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ソースコード長 3940 Byte
File nameファイル名
Exec time実行時間 1285 ms
Memory usageメモリ使用量 71516 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 71 ms 20436 KB
subtask_01_01.txt AC 958 ms 62348 KB
subtask_01_02.txt AC 73 ms 21204 KB
subtask_01_03.txt AC 988 ms 45252 KB
subtask_01_04.txt AC 1227 ms 60000 KB
subtask_01_05.txt AC 200 ms 21992 KB
subtask_01_06.txt AC 194 ms 22904 KB
subtask_01_07.txt AC 1246 ms 71504 KB
subtask_01_08.txt AC 1167 ms 61908 KB
subtask_01_09.txt AC 71 ms 20692 KB
subtask_01_10.txt AC 72 ms 18644 KB
subtask_01_11.txt AC 1119 ms 57216 KB
subtask_01_12.txt AC 1227 ms 60128 KB
subtask_01_13.txt AC 840 ms 49224 KB
subtask_01_14.txt AC 100 ms 21716 KB
subtask_01_15.txt AC 1285 ms 71516 KB
subtask_01_16.txt AC 1179 ms 59952 KB
subtask_01_17.txt AC 792 ms 53520 KB
subtask_01_18.txt AC 886 ms 50652 KB