Submission #423319
Source Code Expand
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.TreeSet; class UnionFindTree{ //各ノードの親を保管するリスト。親がもうない場合は-1。 private int[] ufTree; public UnionFindTree(int num){ ufTree = new int[num]; for(int i = 0; i < num; i++){ ufTree[i] = -1; } } public void doUnion(int a, int b){ if(a == b){return;} int aend = a; int bend = b; while(ufTree[aend] >= 0){ aend = ufTree[aend]; } while(ufTree[bend] >= 0){ bend = ufTree[bend]; } if(aend == bend){ return; }else if(aend > bend){ ufTree[aend] = bend; }else{ ufTree[bend] = aend; } //あるノードの親は、自分より小さい番号になる } public boolean askUnion(int a, int b){ if(a == b){return true;} int aend = a; LinkedList<Integer> pastnodes = new LinkedList<Integer>(); while(ufTree[aend] >= 0){ pastnodes.push(aend); aend = ufTree[aend]; } while(!pastnodes.isEmpty()){ int pastnode = pastnodes.pop(); ufTree[pastnode] = aend; } int bend = b; while(ufTree[bend] >= 0){ pastnodes.push(bend); bend = ufTree[bend]; } while(!pastnodes.isEmpty()){ int pastnode = pastnodes.pop(); ufTree[pastnode] = bend; } return aend == bend; } } public class Main { public static void main(String[] args) { InputReader sc = new InputReader(System.in); int n = sc.nextInt(); int qnum = sc.nextInt(); UnionFindTree u = new UnionFindTree(n); for(int qcount = 0; qcount < qnum; qcount++){ int qnumber = sc.nextInt(); int a = sc.nextInt(); int b = sc.nextInt(); if(qnumber == 0){ u.doUnion(a, b); }else{ System.out.println(u.askUnion(a, b) ? "Yes" : "No"); } } } //nextChar を追加したよ! //System.out.printf("? %d %d\n", i, j); // LinkedList<Integer>[] setsu = new LinkedList[n]; // for(int i = 0; i < n; i++){ // setsu[i] = new LinkedList<Integer>(); // } //ここからテンプレ static class InputReader { private InputStream stream; private byte[] buf = new byte[1024]; private int curChar; private int numChars; private SpaceCharFilter filter; public InputReader(InputStream stream) { this.stream = stream; } public int next() { if (numChars == -1) throw new InputMismatchException(); if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } public String nextStr() { int c = next(); while(isSpaceChar(c)){c = next();} StringBuffer str = new StringBuffer(); do{ str.append((char)c); c = next(); }while(!isSpaceChar(c)); return str.toString(); } public char nextChar() { int c = next(); while(isSpaceChar(c)){c = next();} char ret; do{ ret = (char)c; c = next(); }while(!isSpaceChar(c)); return ret; } public int nextInt() { int c = next(); while (isSpaceChar(c)) c = next(); int sgn = 1; if (c == '-') { sgn = -1; c = next(); } int res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res *= 10; res += c - '0'; c = next(); } while (!isSpaceChar(c)); return res * sgn; } public boolean isSpaceChar(int c) { if (filter != null) return filter.isSpaceChar(c); return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } public interface SpaceCharFilter { public boolean isSpaceChar(int ch); } } }
Submission Info
Submission Time | |
---|---|
Task | B - Union Find |
User | fuzuiR |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 4551 Byte |
Status | AC |
Exec Time | 2451 ms |
Memory | 48348 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 | 528 ms | 27124 KB |
subtask_01_01.txt | AC | 1665 ms | 37848 KB |
subtask_01_02.txt | AC | 370 ms | 27360 KB |
subtask_01_03.txt | AC | 1909 ms | 38088 KB |
subtask_01_04.txt | AC | 2389 ms | 48244 KB |
subtask_01_05.txt | AC | 615 ms | 30484 KB |
subtask_01_06.txt | AC | 602 ms | 31068 KB |
subtask_01_07.txt | AC | 2036 ms | 38304 KB |
subtask_01_08.txt | AC | 2240 ms | 48284 KB |
subtask_01_09.txt | AC | 365 ms | 27056 KB |
subtask_01_10.txt | AC | 371 ms | 27496 KB |
subtask_01_11.txt | AC | 2233 ms | 38180 KB |
subtask_01_12.txt | AC | 2422 ms | 48348 KB |
subtask_01_13.txt | AC | 1938 ms | 38268 KB |
subtask_01_14.txt | AC | 415 ms | 28188 KB |
subtask_01_15.txt | AC | 1914 ms | 38240 KB |
subtask_01_16.txt | AC | 2451 ms | 48308 KB |
subtask_01_17.txt | AC | 1647 ms | 47296 KB |
subtask_01_18.txt | AC | 1415 ms | 47400 KB |