結果
問題 | No.1421 国勢調査 (Hard) |
ユーザー |
![]() |
提出日時 | 2021-03-05 22:11:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,210 bytes |
コンパイル時間 | 1,764 ms |
コンパイル使用メモリ | 173,208 KB |
実行使用メモリ | 5,868 KB |
最終ジャッジ日時 | 2024-10-07 02:16:24 |
合計ジャッジ時間 | 5,730 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 11 WA * 19 |
ソースコード
#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[p][i] > 0){c++;for (int j = 0; j < M; j++){if (j != p && S[j][i] == 1){for (int k = 0; k <= N; k++){S[j][k] ^= S[p][k];}}}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;}}}