結果
問題 | No.1421 国勢調査 (Hard) |
ユーザー |
![]() |
提出日時 | 2021-03-05 22:15:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 64 ms / 2,000 ms |
コード長 | 1,210 bytes |
コンパイル時間 | 1,822 ms |
コンパイル使用メモリ | 173,640 KB |
実行使用メモリ | 5,856 KB |
最終ジャッジ日時 | 2024-10-07 02:26:16 |
合計ジャッジ時間 | 3,645 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int N, M; cin >> N >> M; vector<vector<int>> S(M, vector<int>(N + 1, 0)); for (int i = 0; i < M; i++){ int A; cin >> A; for (int j = 0; j < A; j++){ int B; cin >> B; B--; S[i][B] = 1; } cin >> S[i][N]; } int c = 0; vector<int> id; for (int i = 0; i < N; i++){ int p = c; for (int j = c; j < M; j++){ if (S[j][i] == 1){ p = j; } } swap(S[c], S[p]); if (S[c][i] > 0){ for (int j = 0; j < M; j++){ if (j != c && S[j][i] == 1){ for (int k = 0; k <= N; k++){ S[j][k] ^= S[c][k]; } } } c++; id.push_back(i); } if (c == M){ break; } } int cnt = id.size(); vector<int> X(N, 0); for (int i = 0; i < cnt; i++){ X[id[i]] = S[i][N]; } bool ok = true; for (int i = 0; i < M; i++){ int s = 0; for (int j = 0; j < N; j++){ if (S[i][j] == 1){ s ^= X[j]; } } if (s != S[i][N]){ ok = false; } } if (!ok){ cout << -1 << endl; } else { for (int i = 0; i < N; i++){ cout << X[i] << endl; } } }