Submission #2555742
Source Code Expand
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Main {
private static Scanner sc;
private static int[][] neg8 = new int[][]{{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}};
private static int[][] neg4 = new int[][]{{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
public static void main(String[] args) {
Main instance = new Main();
sc = instance.new Scanner();
instance.solve();
}
private void solve() {
try {
int N = sc.nextInt();
UnionFind uf = new UnionFind(N);
int Q = sc.nextInt();
for (int i = 0; i < Q; i++) {
if (sc.nextInt() == 0) {
uf.unite(sc.nextInt(), sc.nextInt());
} else {
System.out.println(uf.same(sc.nextInt(), sc.nextInt())? "Yes" : "No");
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
private class Scanner {
String[] s;
int i;
BufferedReader br;
String regex = " ";
public Scanner() {
s = new String[0];
i = 0;
br = new BufferedReader(new InputStreamReader(System.in));
}
@Override
protected void finalize() throws Throwable {
try {
super.finalize();
} finally {
destruction();
}
}
private void destruction() throws IOException {
if (br != null) br.close();
}
public String next() throws IOException {
if (i < s.length) return s[i++];
String st = br.readLine();
while (st == "") st = br.readLine();
s = st.split(regex, 0);
i = 0;
return s[i++];
}
public int nextInt() throws NumberFormatException, IOException {
return Integer.parseInt(next());
}
public Long nextLong() throws NumberFormatException, IOException {
return Long.parseLong(next());
}
public Double nextDouble() throws NumberFormatException, IOException {
return Double.parseDouble(next());
}
}
private static double distance(int x1, int x2, int y1, int y2) {
return Math.sqrt((Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2)));
}
private static boolean nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i + 1] <= nums[i]) {
i--;
}
boolean swap = false;
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
swap = true;
}
reverse(nums, i + 1);
return swap;
}
private static void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private static ArrayList filledList(int n, int fill) {
return new ArrayList<>(Collections.nCopies(n, fill));
}
// 指定した値`以上`の要素が最初に現れる位置を返す
private static int lower_bound(List<Integer> list, int val) {
return ~Collections.binarySearch(list, val, (x, y) -> x.compareTo(y) >= 0 ? 1 : -1);
}
// 指定した値`より大きい`の要素が最初に現れる位置を返す
private static int upper_bound(List<Integer> list, int val) {
return ~Collections.binarySearch(list, val, (x, y) -> x.compareTo(y) > 0 ? 1 : -1);
}
private static class Pair<F, S> {
F f;
S s;
Pair() {
}
Pair(F f, S s) {
this.f = f;
this.s = s;
}
Pair(Pair<F, S> p) {
f = p.f;
s = p.s;
}
@Override
public String toString() {
return "{" + f.toString() + ", " + s.toString() + "}";
}
}
private static class UnionFind {
private int par[] = new int[100005];
private UnionFind(int n) {
for (int i = 0; i < n; i++) {
par[i] = i;
}
}
// 木の根を求める
private int find(int x) {
if (par[x] == x) {
return x;
} else {
return par[x] = find(par[x]);
}
}
// xとyの属する集合を併合
private void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
par[x] = y;
}
// xとyが同じ集合に属するか
private boolean same(int x, int y) {
return find(x) == find(y);
}
}
}
Submission Info
Submission Time |
|
Task |
B - Union Find |
User |
jun0sck |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
100 |
Code Size |
5322 Byte |
Status |
AC |
Exec Time |
1276 ms |
Memory |
48380 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 |
81 ms |
19284 KB |
subtask_01_01.txt |
AC |
919 ms |
44248 KB |
subtask_01_02.txt |
AC |
73 ms |
20820 KB |
subtask_01_03.txt |
AC |
1231 ms |
45536 KB |
subtask_01_04.txt |
AC |
1255 ms |
44004 KB |
subtask_01_05.txt |
AC |
269 ms |
27028 KB |
subtask_01_06.txt |
AC |
262 ms |
29040 KB |
subtask_01_07.txt |
AC |
1226 ms |
44172 KB |
subtask_01_08.txt |
AC |
1264 ms |
47080 KB |
subtask_01_09.txt |
AC |
75 ms |
19408 KB |
subtask_01_10.txt |
AC |
84 ms |
21460 KB |
subtask_01_11.txt |
AC |
1265 ms |
45448 KB |
subtask_01_12.txt |
AC |
1275 ms |
46296 KB |
subtask_01_13.txt |
AC |
1074 ms |
48380 KB |
subtask_01_14.txt |
AC |
111 ms |
20564 KB |
subtask_01_15.txt |
AC |
1221 ms |
45316 KB |
subtask_01_16.txt |
AC |
1276 ms |
48080 KB |
subtask_01_17.txt |
AC |
856 ms |
46984 KB |
subtask_01_18.txt |
AC |
869 ms |
47688 KB |