結果
問題 | No.1421 国勢調査 (Hard) |
ユーザー |
![]() |
提出日時 | 2021-03-05 23:07:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 44 ms / 2,000 ms |
コード長 | 1,993 bytes |
コンパイル時間 | 1,087 ms |
コンパイル使用メモリ | 110,116 KB |
最終ジャッジ日時 | 2025-01-19 11:55:11 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <iostream>#include <algorithm>#include <string>#include <vector>#include <cmath>#include <map>#include <queue>#include <iomanip>#include <set>#include <tuple>#define mkp make_pair#define mkt make_tuple#define rep(i,n) for(int i = 0; i < (n); ++i)#define all(v) v.begin(),v.end()using namespace std;typedef long long ll;const ll MOD=1e9+7;template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}vector<int> Gauss(vector<vector<int>> &A){//F2(xor)int N=A.size();int M=A[0].size();int rank=0;for(int j=0;j<M;j++){if(j+1==M) break;int pivot=-1;for(int i=rank;i<N;i++){if(A[i][j]){pivot=i;break;}}if(pivot>=0){if(pivot!=rank){for(int k=0;k<M;k++) swap(A[pivot][k],A[rank][k]);}for(int i=0;i<N;i++){if(i!=rank&&A[i][j]){for(int k=0;k<M;k++) A[i][k]^=A[rank][k];}}rank++;}}vector<int> result;for(int i=rank;i<N;i++) if(A[i][M-1]!=0) return result;result.resize(M-1,0);for(int i=0;i<rank;i++){int tar=-1;for(int j=0;j+1<M;j++){if(A[i][j]!=0){tar=j;break;}}if(tar==-1) continue;result[tar]=A[i][M-1];}return result;}int main(){cin.tie(0);ios::sync_with_stdio(false);int N,M;cin>>N>>M;vector<vector<int>> A(M,vector<int> (N+1,0));rep(q,M){int K;cin>>K;vector<int> B(K);rep(i,K) cin>>B[i];rep(i,K) B[i]--;int value;cin>>value;rep(i,K) A[q][B[i]]=1;A[q][N]=value;}vector<int> ans=Gauss(A);if(ans.empty()){cout<<-1<<endl;return 0;}for(auto n:ans) cout<<n<<"\n";return 0;}