結果
問題 |
No.1420 国勢調査 (Easy)
|
ユーザー |
![]() |
提出日時 | 2021-03-09 20:19:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 75 ms / 2,000 ms |
コード長 | 1,484 bytes |
コンパイル時間 | 4,114 ms |
コンパイル使用メモリ | 231,740 KB |
実行使用メモリ | 11,776 KB |
最終ジャッジ日時 | 2024-10-11 12:33:33 |
合計ジャッジ時間 | 8,550 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include "bits/stdc++.h" #include "atcoder/all" using namespace std; using namespace atcoder; //using mint = modint1000000007; //const int mod = 1000000007; //using mint = modint998244353; //const int mod = 998244353; //const int INF = 1e9; //const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define rrep(i, n) for (int i = (n-1); i >= 0; --i) #define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i) #define all(x) (x).begin(),(x).end() #define allR(x) (x).rbegin(),(x).rend() #define endl "\n" int Ans[100005]; bool check[100005]; struct Edge { int to, id; Edge(int to, int id) :to(to), id(id) {} }; vector<Edge>g[100005]; bool b; void dfs(int v, int p = -1) { //cout << "noe" << v << endl; check[v] = true; for (Edge e : g[v]) { //cout << "next" << e.to << endl; if (p == e.to) { continue; } int next = Ans[v] ^ e.id; //cout << "point" << next << endl; if (check[e.to]) { if (next != Ans[e.to]) { b = false; } } else { Ans[e.to] = next; dfs(e.to, v); } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; dsu uf(N); rep(i, M) { int a, b, c; cin >> a >> b >> c; a--; b--; g[a].emplace_back(b, c); g[b].emplace_back(a, c); uf.merge(a, b); } b = true; rep(i, N) { if (i == uf.leader(i)) { Ans[i] = 0; dfs(i); } } if (!b) { cout << -1 << endl; return 0; } rep(i, N) { cout << Ans[i] << endl; } return 0; }