Submission #423603
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; LinkedList<Integer> pasta = new LinkedList<Integer>(); LinkedList<Integer> pastb = new LinkedList<Integer>(); pasta.push(aend); pastb.push(bend); while(ufTree[aend] >= 0){ aend = ufTree[aend]; pasta.push(aend); } while(ufTree[bend] >= 0){ bend = ufTree[bend]; pastb.push(bend); } if(aend == bend){ return; }else if(aend > bend){ while(!pasta.isEmpty()){ int anode = pasta.pop(); ufTree[anode] = bend; } }else{ while(!pastb.isEmpty()){ int bnode = pastb.pop(); ufTree[bnode] = aend; } } //あるノードの親は、自分より小さい番号になる } public boolean ask(int a, int b){ if(a == b){return true;} int aend = a; while(ufTree[aend] >= 0){ aend = ufTree[aend]; } int bend = b; while(ufTree[bend] >= 0){ bend = ufTree[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.ask(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 | Java (OpenJDK 1.7.0) |
Score | 100 |
Code Size | 4563 Byte |
Status | AC |
Exec Time | 2269 ms |
Memory | 35984 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 | 449 ms | 22260 KB |
subtask_01_01.txt | AC | 1615 ms | 35208 KB |
subtask_01_02.txt | AC | 380 ms | 23188 KB |
subtask_01_03.txt | AC | 2269 ms | 34836 KB |
subtask_01_04.txt | AC | 2052 ms | 35608 KB |
subtask_01_05.txt | AC | 846 ms | 28324 KB |
subtask_01_06.txt | AC | 866 ms | 29528 KB |
subtask_01_07.txt | AC | 2095 ms | 34420 KB |
subtask_01_08.txt | AC | 2238 ms | 35532 KB |
subtask_01_09.txt | AC | 366 ms | 22068 KB |
subtask_01_10.txt | AC | 387 ms | 23316 KB |
subtask_01_11.txt | AC | 2112 ms | 34732 KB |
subtask_01_12.txt | AC | 2143 ms | 35112 KB |
subtask_01_13.txt | AC | 1796 ms | 35360 KB |
subtask_01_14.txt | AC | 389 ms | 23824 KB |
subtask_01_15.txt | AC | 2082 ms | 34972 KB |
subtask_01_16.txt | AC | 2150 ms | 35900 KB |
subtask_01_17.txt | AC | 1561 ms | 35804 KB |
subtask_01_18.txt | AC | 1584 ms | 35984 KB |