結果
問題 |
No.1421 国勢調査 (Hard)
|
ユーザー |
![]() |
提出日時 | 2021-03-05 23:39:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 23 ms / 2,000 ms |
コード長 | 1,619 bytes |
コンパイル時間 | 828 ms |
コンパイル使用メモリ | 93,408 KB |
最終ジャッジ日時 | 2025-01-19 12:03:28 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> using namespace std; using ll = long long; struct P { P &operator^=(const P &p) { b ^= p.b; y ^= p.y; return *this; } ll b; int y; }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<P> p(m); for (int i = 0; i < m; i++) { int a; cin >> a; ll b = 0; for (int j = 0; j < a; j++) { int k; cin >> k; k--; b ^= 1LL << k; } int y; cin >> y; p[i] = { b, y }; } for (int k = 0; k < n; k++) { ll t = 1LL << k; int f = 0; for (int i = k; i < m; i++) { if (p[i].b & t) { for (int i1 = i + 1; i1 < m; i1++) { if (p[i1].b & t) p[i1] ^= p[i]; } swap(p[i], p[k]); f = 1; break; } } if (f == 0) { p.push_back({ t, 0 }); m++; swap(p.back(), p[k]); } } for (int i = 0; i < m; i++) { if (p[i].b == 0 && p[i].y != 0) { cout << -1 << endl; exit(0); } } for (int i = n; --i >= 0;) { for (int i1 = 0; i1 < i; i1++) { if (p[i].b & p[i1].b) { p[i1] ^= p[i]; } } } for (int i = 0; i < n; i++) { cout << p[i].y << '\n'; } return 0; }