結果

問題 No.2236 Lights Out On Simple Graph
ユーザー tnakao0123
提出日時 2024-07-04 20:01:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,091 ms / 4,000 ms
コード長 1,667 bytes
コンパイル時間 659 ms
コンパイル使用メモリ 66,472 KB
最終ジャッジ日時 2025-02-22 01:57:41
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:35:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   35 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
main.cpp:39:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   39 |     scanf("%d%d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~
main.cpp:47:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   47 |     scanf("%d", &ci);
      |     ~~~~~^~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 2236.cc:  No.2236 Lights Out On Simple Graph - yukicoder
 */

#include<cstdio>
#include<unordered_map>
#include<algorithm>
 
using namespace std;

/* constant */

const int MAX_N = 40;
const int MAX_M = 40;
const int MAX_K = MAX_M / 2;
const int KBITS = 1 << MAX_K;
const int INF = 1 << 30;

/* typedef */

using ll = long long;
using umli = unordered_map<ll,int>;

/* global variables */

ll es[MAX_M];

/* subroutines */

/* main */

int main() {
  int n, m;
  scanf("%d%d", &n, &m);

  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--, v--;
    es[i] = (1LL << u) | (1LL << v);
  }

  ll st = 0;
  for (int i = 0; i < n; i++) {
    int ci;
    scanf("%d", &ci);
    st |= (ll)ci << i;
  }

  int k0 = m / 2, k1 = m - k0;
  int kbits0 = 1 << k0, kbits1 = 1 << k1;

  umli scs0, scs1;
  for (int bits = 0; bits < kbits0; bits++) {
    ll s = 0;
    int c = 0;
    for (int i = 0, bi = 1; i < k0; i++, bi <<= 1)
      if (bits & bi) s ^= es[i], c++;
    if (! scs0.count(s)) scs0[s] = c;
    else scs0[s] = min(scs0[s], c);
  }
  for (int bits = 0; bits < kbits1; bits++) {
    ll s = 0;
    int c = 0;
    for (int i = 0, bi = 1; i < k1; i++, bi <<= 1)
      if (bits & bi) s ^= es[k0 + i], c++;
    if (! scs1.count(s)) scs1[s] = c;
    else scs1[s] = min(scs1[s], c);
  }
  //for (auto [s, c]: scs0) printf(" %lld,%d", s, c); putchar('\n');
  //for (auto [s, c]: scs1) printf(" %lld,%d", s, c); putchar('\n');

  int minc = INF;
  for (auto [s0, c0]: scs0) {
    ll s1 = st ^ s0;
    if (scs1.count(s1)) minc = min(minc, c0 + scs1[s1]);
  }

  printf("%d\n", (minc < INF) ? minc : -1);
  
  return 0;
}
0