結果
問題 | No.2236 Lights Out On Simple Graph |
ユーザー |
![]() |
提出日時 | 2023-03-03 22:28:13 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,561 ms / 4,000 ms |
コード長 | 1,135 bytes |
コンパイル時間 | 12,928 ms |
コンパイル使用メモリ | 284,360 KB |
最終ジャッジ日時 | 2025-02-11 03:11:49 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
#pragma GCC target("avx")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>using namespace std;int main() {cin.tie(0);ios::sync_with_stdio(false);int N, M;cin >> N >> M;long long state_init = 0;vector<int> a(M), b(M);for( int i = 0; i < M; i++ ) {cin >> a[i] >> b[i];a[i]--, b[i]--;}for( int i = 0; i < N; i++ ) {long long c;cin >> c;state_init |= c<<i;}int m1 = M/2, m2 = (M+1)/2, ans = 100;map<long long, int> mp;for( int S = 0; S < 1<<m1; S++ ) {long long state = 0;for( int i = 0; i < m1; i++ ) {if( (S>>i)&1 ) {state ^= 1LL<<a[i];state ^= 1LL<<b[i];}}if( !mp.count(state) ) {mp[state] = M;}mp[state] = min(mp[state], __builtin_popcount(S));}for( int S = 0; S < 1<<m2; S++ ) {long long state = 0;for( int i = m1; i < m1+m2; i++ ) {if( (S>>(i-m1))&1 ) {state ^= 1LL<<a[i];state ^= 1LL<<b[i];}}if( mp.count(state^state_init) ) {ans = min(ans, mp[state^state_init]+__builtin_popcount(S));}}if( ans == 100 ) {cout << -1 << endl;}else {cout << ans << endl;}}