結果
問題 | No.1420 国勢調査 (Easy) |
ユーザー |
![]() |
提出日時 | 2021-03-13 16:32:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 78 ms / 2,000 ms |
コード長 | 1,490 bytes |
コンパイル時間 | 846 ms |
コンパイル使用メモリ | 97,400 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-10-15 07:27:04 |
合計ジャッジ時間 | 6,390 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
/* -*- coding: utf-8 -*-** 1420.cc: No.1420 国勢調査 (Easy) - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_N = 100000;/* typedef */typedef pair<int,int> pii;typedef vector<pii> vpii;/* global variables */vpii nbrs[MAX_N];bool used[MAX_N];int ps[MAX_N], cis[MAX_N], xs[MAX_N];/* subroutines *//* main */int main() {int n, m;scanf("%d%d", &n, &m);for (int i = 0; i < m; i++) {int u, v, y;scanf("%d%d%d", &u, &v, &y);u--, v--;nbrs[u].push_back(pii(v, y));nbrs[v].push_back(pii(u, y));}for (int st = 0; st < n; st++)if (! used[st]) {used[st] = true;ps[st] = -1;xs[st] = 0;for (int u = st; u >= 0;) {vpii &nbru = nbrs[u];if (cis[u] < nbru.size() && nbru[cis[u]].first == ps[u]) cis[u]++;if (cis[u] < nbru.size()) {pii ve = nbru[cis[u]++];int v = ve.first, y = ve.second;if (! used[v]) {used[v] = true;ps[v] = u, xs[v] = xs[u] ^ y;u = v;}else {if ((xs[u] ^ xs[v]) != y) { puts("-1"); return 0; }}}else {u = ps[u];}}}for (int i = 0; i < n; i++) printf("%d\n", xs[i]);return 0;}