Submission #5360761
Source Code Expand
import java.io.IOException; import java.io.InputStream; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); 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]); } } 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]++; } } } boolean isEquivalent(int x, int y){ return find(x) == find(y); } int peersnum(int x){ return peers[find(x)]; } }
Submission Info
Submission Time | |
---|---|
Task | B - Union Find |
User | warachia |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 1652 Byte |
Status | AC |
Exec Time | 1599 ms |
Memory | 160416 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01.txt |
All | 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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 111 ms | 21204 KB |
subtask_01_01.txt | AC | 1092 ms | 95868 KB |
subtask_01_02.txt | AC | 95 ms | 21332 KB |
subtask_01_03.txt | AC | 1509 ms | 158144 KB |
subtask_01_04.txt | AC | 1552 ms | 158488 KB |
subtask_01_05.txt | AC | 408 ms | 47336 KB |
subtask_01_06.txt | AC | 406 ms | 45620 KB |
subtask_01_07.txt | AC | 1519 ms | 154272 KB |
subtask_01_08.txt | AC | 1597 ms | 156852 KB |
subtask_01_09.txt | AC | 112 ms | 20564 KB |
subtask_01_10.txt | AC | 113 ms | 22868 KB |
subtask_01_11.txt | AC | 1529 ms | 160416 KB |
subtask_01_12.txt | AC | 1599 ms | 156568 KB |
subtask_01_13.txt | AC | 1331 ms | 156516 KB |
subtask_01_14.txt | AC | 152 ms | 25572 KB |
subtask_01_15.txt | AC | 1555 ms | 156456 KB |
subtask_01_16.txt | AC | 1570 ms | 156536 KB |
subtask_01_17.txt | AC | 1227 ms | 157936 KB |
subtask_01_18.txt | AC | 1210 ms | 158448 KB |