結果
問題 | No.1054 Union add query |
ユーザー | jp_ste |
提出日時 | 2020-05-17 04:14:21 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,589 ms / 2,000 ms |
コード長 | 1,315 bytes |
コンパイル時間 | 2,187 ms |
コンパイル使用メモリ | 77,424 KB |
実行使用メモリ | 79,704 KB |
最終ジャッジ日時 | 2023-10-24 17:44:58 |
合計ジャッジ時間 | 17,231 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 122 ms
57,656 KB |
testcase_01 | AC | 144 ms
57,824 KB |
testcase_02 | AC | 113 ms
56,228 KB |
testcase_03 | AC | 1,570 ms
76,644 KB |
testcase_04 | AC | 1,580 ms
78,176 KB |
testcase_05 | AC | 1,535 ms
76,812 KB |
testcase_06 | AC | 1,589 ms
76,552 KB |
testcase_07 | AC | 1,513 ms
76,700 KB |
testcase_08 | AC | 1,565 ms
74,748 KB |
testcase_09 | AC | 1,549 ms
79,704 KB |
testcase_10 | AC | 1,375 ms
78,572 KB |
ソースコード
import java.util.Arrays; import java.util.Scanner; public class Main { static Scanner scan = new Scanner(System.in); 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) { union.unite(A-1, B-1); } else if(T == 2) { union.add(A-1, B); } else if(T == 3) { union.out(A-1); } } union.flush(); } } class UnionFind { int[] L; long[] V; StringBuilder sb = new StringBuilder(); 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; } void out(int x) { long ans = 0; while(true){ ans += V[x]; x = L[x]; if(x < 0) break; } sb.append(ans); sb.append("\n"); } void flush() { System.out.println(sb.toString().trim()); } }