結果
問題 | No.1420 国勢調査 (Easy) |
ユーザー |
![]() |
提出日時 | 2021-03-05 21:46:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,315 bytes |
コンパイル時間 | 821 ms |
コンパイル使用メモリ | 88,384 KB |
実行使用メモリ | 14,592 KB |
最終ジャッジ日時 | 2024-10-07 01:20:35 |
合計ジャッジ時間 | 12,030 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | WA * 30 |
ソースコード
#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, 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));}dfs(1, 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;}