結果
問題 | No.1420 国勢調査 (Easy) |
ユーザー |
![]() |
提出日時 | 2021-03-05 21:48:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,381 bytes |
コンパイル時間 | 973 ms |
コンパイル使用メモリ | 88,532 KB |
実行使用メモリ | 17,860 KB |
最終ジャッジ日時 | 2024-10-07 01:23:52 |
合計ジャッジ時間 | 9,253 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 12 WA * 18 |
ソースコード
#include <iostream>#include <set>#include <map>#include <cmath>#include <queue>#include <vector>#include <string>#include <algorithm>#include <functional>using namespace std;int N, M;int A[1 << 18], B[1 << 18], Y[1 << 18];int Answer[1 << 18];int col[1 << 18];bool used[1 << 18], flag = false;vector<pair<int, int>> G[1 << 18];void dfs(int pos, int dep) {used[pos] = true;col[pos] = dep;for (int i = 0; i < G[pos].size(); i++) {int to = G[pos][i].first;int cost = G[pos][i].second;if (used[to] == true) {if (col[to] != (cost ^ dep)) flag = true;return;}else {dfs(to, (dep ^ cost));}}}int main() {// Step 1. 入力cin >> N >> M;for (int i = 1; i <= M; i++) {cin >> A[i] >> B[i] >> Y[i];}// Step #2. ビットごとに計算for (int i = 0; i < 30; i++) {for (int j = 1; j <= N; j++) G[j].clear();for (int j = 1; j <= N; j++) used[j] = false;for (int j = 1; j <= M; j++) {int t = (Y[j] / (1 << i)) % 2;G[A[j]].push_back(make_pair(B[j], t));G[B[j]].push_back(make_pair(A[j], t));}for (int j = 1; j <= N; j++) {if (used[j] == false) dfs(j, 0);}for (int j = 1; j <= N; j++) {if (col[j] == 1) Answer[j] += (1 << i);}}// Step #3. 出力if (flag == true) {cout << "-1" << endl;}else {for (int i = 1; i <= N; i++) cout << Answer[i] << endl;}return 0;}