結果
問題 | No.1420 国勢調査 (Easy) |
ユーザー |
![]() |
提出日時 | 2021-03-06 15:11:11 |
言語 | Java (openjdk 23) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,955 bytes |
コンパイル時間 | 4,174 ms |
コンパイル使用メモリ | 77,416 KB |
実行使用メモリ | 52,280 KB |
最終ジャッジ日時 | 2024-10-08 14:19:42 |
合計ジャッジ時間 | 22,533 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 12 WA * 18 |
ソースコード
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();UnionFindTree uft = new UnionFindTree(n);for (int i = 0; i < m; i++) {int a = sc.nextInt() - 1;int b = sc.nextInt() - 1;int c = sc.nextInt();if (uft.same(a, b)) {if (uft.get(a, b) != c) {System.out.println(-1);return;}} else {uft.unite(a, b, c);}}StringBuilder sb = new StringBuilder();for (int i = 0; i < n; i++) {sb.append(uft.getCost(i)).append("\n");}System.out.print(sb);}static class UnionFindTree {int[] parents;int[] costs;public UnionFindTree(int size) {parents = new int[size];costs = new int[size];for (int i = 0; i < size; i++) {parents[i] = i;}}public int find(int x) {if (x == parents[x]) {return x;} else {int tmp = find(parents[x]);costs[x] ^= costs[parents[x]];return parents[x] = tmp;}}public int get(int x, int y) {find(x);find(y);return costs[x] ^ costs[y];}public boolean same(int x, int y) {return find(x) == find(y);}public int getCost(int x) {find(x);return costs[x];}public void unite(int x, int y, int c) {int xx = find(x);int yy = find(y);parents[xx] = yy;costs[xx] = costs[x] ^ c;}}}