Submission #101916
Source Code Expand
import java.io.IOException; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; public class Main { static class UnionFind { final int tree[]; public UnionFind(int n) { this.tree = new int[n]; Arrays.fill(tree, -1); } void union(int x, int y) { x = root(x); y = root(y); if(x != y) { if(tree[x] > tree[y]) { x ^= y; y ^= x; x ^= y; } tree[x] += tree[y]; tree[y] = x; } } boolean find(int x, int y) { return root(x) == root(y); } int root(int x) { return tree[x] < 0 ? x : (tree[x] = root(tree[x])); } } public static void main(String[] args) { int N = nextInt(); int M = nextInt(); int K = nextInt(); int e[][] = new int[M][]; for(int i = 0; i < M; i++) e[i] = new int[]{nextInt()-1, nextInt()-1}; boolean dt[] = new boolean[M]; int Q[][] = new int[K][]; for(int i = 0; i < K; i++) { int q = nextInt(); if(q == 0) { Q[i] = new int[]{q, nextInt()-1}; dt[Q[i][1]] = true; } else { Q[i] = new int[]{q, nextInt()-1, nextInt()-1}; } } UnionFind uf = new UnionFind(N); for(int i = 0; i < M; i++) if(!dt[i]) { uf.union(e[i][0], e[i][1]); } ArrayList<Boolean> ans = new ArrayList<Boolean>(); for(int i = K-1; i >= 0; i--) { if(Q[i][0] == 0) { uf.union(e[Q[i][1]][0], e[Q[i][1]][1]); } else { ans.add(uf.find(Q[i][1], Q[i][2])); } } PrintWriter pw = new PrintWriter(System.out); for(int i = ans.size()-1; i >= 0; i--) pw.println(ans.get(i) ? "YES" : "NO"); pw.close(); } static int nextInt() { int c = 0; try { c = System.in.read(); while(c != '-' && (c < '0' || c > '9')) c = System.in.read(); if(c == '-') return -nextInt(); int res = 0; while(c >= '0' && c <= '9') { res = res*10 + c-'0'; c = System.in.read(); } return res; } catch (IOException e) { // TODO 自動生成された catch ブロック e.printStackTrace(); } return -1; } }
Submission Info
Submission Time | |
---|---|
Task | D - Graph Destruction |
User | TowersofHanoi |
Language | Java (OpenJDK 1.7.0) |
Score | 100 |
Code Size | 2076 Byte |
Status | AC |
Exec Time | 1172 ms |
Memory | 37244 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 32, 33, 34, 35, 36, 4, 5, 50, 6, 7, 8, 9 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
1 | AC | 421 ms | 20652 KB |
10 | AC | 434 ms | 22328 KB |
11 | AC | 483 ms | 23948 KB |
12 | AC | 546 ms | 25480 KB |
13 | AC | 550 ms | 27356 KB |
14 | AC | 580 ms | 28764 KB |
15 | AC | 1172 ms | 30196 KB |
16 | AC | 688 ms | 37244 KB |
17 | AC | 540 ms | 26136 KB |
18 | AC | 542 ms | 25548 KB |
19 | AC | 547 ms | 26160 KB |
2 | AC | 404 ms | 20660 KB |
20 | AC | 572 ms | 27816 KB |
21 | AC | 540 ms | 26336 KB |
22 | AC | 576 ms | 27616 KB |
23 | AC | 559 ms | 26380 KB |
24 | AC | 526 ms | 25068 KB |
25 | AC | 521 ms | 25448 KB |
26 | AC | 615 ms | 29208 KB |
27 | AC | 517 ms | 24720 KB |
28 | AC | 540 ms | 25256 KB |
29 | AC | 570 ms | 27808 KB |
3 | AC | 406 ms | 20664 KB |
30 | AC | 556 ms | 26860 KB |
31 | AC | 610 ms | 29556 KB |
32 | AC | 560 ms | 27716 KB |
33 | AC | 582 ms | 28784 KB |
34 | AC | 626 ms | 29376 KB |
35 | AC | 607 ms | 29072 KB |
36 | AC | 584 ms | 26196 KB |
4 | AC | 421 ms | 20664 KB |
5 | AC | 411 ms | 20652 KB |
50 | AC | 596 ms | 28848 KB |
6 | AC | 444 ms | 20664 KB |
7 | AC | 414 ms | 20660 KB |
8 | AC | 415 ms | 20776 KB |
9 | AC | 433 ms | 20788 KB |