結果
問題 | No.1054 Union add query |
ユーザー | jp_ste |
提出日時 | 2020-05-17 04:58:11 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,921 ms / 2,000 ms |
コード長 | 1,319 bytes |
コンパイル時間 | 4,117 ms |
コンパイル使用メモリ | 77,296 KB |
実行使用メモリ | 79,564 KB |
最終ジャッジ日時 | 2023-10-24 18:48:41 |
合計ジャッジ時間 | 18,831 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 136 ms
57,588 KB |
testcase_01 | AC | 143 ms
57,696 KB |
testcase_02 | AC | 136 ms
57,440 KB |
testcase_03 | AC | 1,875 ms
72,428 KB |
testcase_04 | AC | 1,921 ms
79,564 KB |
testcase_05 | AC | 1,883 ms
72,308 KB |
testcase_06 | AC | 1,867 ms
74,620 KB |
testcase_07 | AC | 1,785 ms
75,128 KB |
testcase_08 | AC | 1,854 ms
75,404 KB |
testcase_09 | AC | 1,879 ms
78,472 KB |
testcase_10 | AC | 1,508 ms
78,712 KB |
ソースコード
import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; public class Main { static Scanner scan = new Scanner(System.in); static PrintWriter pw = new PrintWriter(System.out); static UnionFind union; static int N, Q; public static void main(String[] args) { N = scan.nextInt(); Q = scan.nextInt(); union = new UnionFind(N); for(int i=0; i<Q; i++) { int T = scan.nextInt(); int A = scan.nextInt(); int B = scan.nextInt(); if(T == 1) { if(union.same(A-1, B-1)) continue; union.unite(A-1, B-1); } else if(T == 2) { union.add(A-1, B); } else if(T == 3) { pw.println(union.out(A-1)); } } pw.close(); } } class UnionFind { int[] L; long[] V; UnionFind(int N) { L = new int[N]; V = new long[N]; Arrays.fill(L, -1); } int root(int x) { return L[x] < 0 ? x : root(L[x]); } boolean same(int x, int y) { return root(x) == root(y); } void unite(int x, int y) { x = root(x); y = root(y); if (x == y) { return; } if (L[x] < L[y]) { int w = x; x = y; y = w; } L[y] += L[x]; L[x] = y; V[x] -= V[y]; } void add(int x, int value) { x = root(x); V[x] += value; } long out(int x) { long ans = 0; while(true){ ans += V[x]; x = L[x]; if(x < 0) break; } return ans; } }