#849064 (C++17) No.421 しろくろチョコレート

• 問題: No.421 しろくろチョコレート
• ユーザー: hashiryo
• 提出日時: 2023-03-14 16:05:24
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 3 ms / 2,000 ms
• コード長: 5,627 bytes
• コンパイル時間: 2,637 ms
• コンパイル使用メモリ: 220,324 KB
• 実行使用メモリ: 4,348 KB
• 最終ジャッジ日時: 2023-10-18 11:46:01
• 合計ジャッジ時間: 4,506 ms
• ジャッジサーバーID （参考情報）: judge13 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,348 KB
testcase_01	AC	2 ms; 4,348 KB
testcase_02	AC	3 ms; 4,348 KB
testcase_03	AC	3 ms; 4,348 KB
testcase_04	AC	2 ms; 4,348 KB
testcase_05	AC	3 ms; 4,348 KB
testcase_06	AC	2 ms; 4,348 KB
testcase_07	AC	2 ms; 4,348 KB
testcase_08	AC	2 ms; 4,348 KB
testcase_09	AC	2 ms; 4,348 KB
testcase_10	AC	2 ms; 4,348 KB
testcase_11	AC	2 ms; 4,348 KB
testcase_12	AC	2 ms; 4,348 KB
testcase_13	AC	2 ms; 4,348 KB
testcase_14	AC	2 ms; 4,348 KB
testcase_15	AC	2 ms; 4,348 KB
testcase_16	AC	3 ms; 4,348 KB
testcase_17	AC	3 ms; 4,348 KB
testcase_18	AC	2 ms; 4,348 KB
testcase_19	AC	2 ms; 4,348 KB
testcase_20	AC	3 ms; 4,348 KB
testcase_21	AC	2 ms; 4,348 KB
testcase_22	AC	2 ms; 4,348 KB
testcase_23	AC	2 ms; 4,348 KB
testcase_24	AC	2 ms; 4,348 KB
testcase_25	AC	2 ms; 4,348 KB
testcase_26	AC	2 ms; 4,348 KB
testcase_27	AC	2 ms; 4,348 KB
testcase_28	AC	3 ms; 4,348 KB
testcase_29	AC	3 ms; 4,348 KB
testcase_30	AC	2 ms; 4,348 KB
testcase_31	AC	3 ms; 4,348 KB
testcase_32	AC	2 ms; 4,348 KB
testcase_33	AC	2 ms; 4,348 KB
testcase_34	AC	2 ms; 4,348 KB
testcase_35	AC	2 ms; 4,348 KB
testcase_36	AC	2 ms; 4,348 KB
testcase_37	AC	3 ms; 4,348 KB
testcase_38	AC	3 ms; 4,348 KB
testcase_39	AC	2 ms; 4,348 KB
testcase_40	AC	2 ms; 4,348 KB
testcase_41	AC	2 ms; 4,348 KB
testcase_42	AC	2 ms; 4,348 KB
testcase_43	AC	2 ms; 4,348 KB
testcase_44	AC	2 ms; 4,348 KB
testcase_45	AC	3 ms; 4,348 KB
testcase_46	AC	2 ms; 4,348 KB
testcase_47	AC	2 ms; 4,348 KB
testcase_48	AC	2 ms; 4,348 KB
testcase_49	AC	2 ms; 4,348 KB
testcase_50	AC	3 ms; 4,348 KB
testcase_51	AC	3 ms; 4,348 KB
testcase_52	AC	2 ms; 4,348 KB
testcase_53	AC	2 ms; 4,348 KB
testcase_54	AC	2 ms; 4,348 KB
testcase_55	AC	2 ms; 4,348 KB
testcase_56	AC	2 ms; 4,348 KB
testcase_57	AC	3 ms; 4,348 KB
testcase_58	AC	3 ms; 4,348 KB
testcase_59	AC	2 ms; 4,348 KB
testcase_60	AC	3 ms; 4,348 KB
testcase_61	AC	3 ms; 4,348 KB
testcase_62	AC	2 ms; 4,348 KB
testcase_63	AC	2 ms; 4,348 KB
testcase_64	AC	2 ms; 4,348 KB

ソースコード

#include <bits/stdc++.h>
// clang-format off
std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
std::ostream&operator<<(std::ostream&os,const __uint128_t &v){if(!v)os<<"0";__uint128_t tmp=v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}

#define checkpoint() (void(0))
#define debug(x) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
#ifdef __LOCAL
// clang-format off
#undef checkpoint
#undef debug
#undef debugArray
#undef debugMatrix
template<class T, class U>std::ostream &operator<<(std::ostream&os,const std::pair<T,U>&x){return os<<"("<<x.first<<", "<<x.second<<")";}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::vector<T>&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<<vec[_];return os<<']';}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::set<T>&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<<x; return os << '}';}
template<typename T,std::size_t _Nm>std::ostream&operator<<(std::ostream &os,const std::array<T, _Nm> &arr) {os<<'['<<arr[0];for(std::size_t _=1;_<_Nm;++_)os<<", "<<arr[_];return os<<']';}
template<class Tup,std::size_t... I>void print(std::ostream&os,const Tup &x,std::index_sequence<I...>){(void)(int[]){(os<<std::get<I>(x)<<", ",0)...};}
template<class... Args>std::ostream &operator<<(std::ostream&os,const std::tuple<Args...> &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence<N-1>());return os<<std::get<N-1>(x)<<")";}
const std::string COLOR_RESET="\033[0m",BRIGHT_GREEN="\033[1;32m",BRIGHT_RED="\033[1;31m",BRIGHT_CYAN="\033[1;36m",NORMAL_CROSSED="\033[0;9;37m",ITALIC="\033[3m",BOLD="\033[1m",RED_BACKGROUND="\033[1;41m",NORMAL_FAINT="\033[0;2m";
#define func_LINE_FILE  NORMAL_FAINT<<" in "<<BOLD<<__func__<<NORMAL_FAINT<<ITALIC<<" (L"<<__LINE__<<") "<< __FILE__<<COLOR_RESET
#define checkpoint() std::cerr<<BRIGHT_RED<<"< check point! >"<<func_LINE_FILE<<'\n'
#define debug(x) std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = "<<(x)<<func_LINE_FILE<<'\n'
#define debugArray(x, n) do{std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = ["<<x[0];for(int _=1;_<(int)(n);++_)std::cerr<<", "<<x[_];std::cerr<<"]"<<func_LINE_FILE<<'\n';}while(0)
#define debugMatrix(x, h, w) do{std::cerr<<BRIGHT_CYAN<<#x<<"\n"<<COLOR_RESET<<"= ";for(int _=0;(_)<(int)(h);++_){std::cerr<<((_?"   [":"[["));for(int __=0;__<(int)(w);++__)std::cerr<<((__?", ":""))<<x[_][__];std::cerr<<"]"<<(_+1==(int)(h)?"]":",\n");}std::cerr<<func_LINE_FILE<<'\n';}while(0)
#endif
// clang-format on

class Matching {
 int n, ret;
 std::vector<std::vector<int>> adj;
 std::vector<int> mt, idx, p;
 std::vector<std::array<int, 2>> es;
 void rematch(int u, int v, int w= -1) {
  if (w= mt[u], mt[u]= v; w == -1 || mt[w] != u) return;
  if (es[u][1] == -1) {
   rematch(mt[w]= es[u][0], w);
  } else rematch(es[u][0], es[u][1]), rematch(es[u][1], es[u][0]);
 }
 int f(int x) { return (idx[x] != ret || p[x] == -1) ? x : (p[x]= f(p[x])); }
 bool check(int root) {
  std::queue<int> que;
  es[root]= {-1, -1}, idx[root]= ret, p[root]= -1, que.push(root);
  for (int x, u, v, w; !que.empty();) {
   x= que.front(), que.pop();
   for (int y: adj[x]) {
    if (y == root) continue;
    if (mt[y] == -1) {
     return rematch(mt[y]= x, y), true;
    } else if (idx[y] == ret) {
     if (u= f(x), v= f(y), w= root; u == v) continue;
     for (; u != root || v != root; es[u]= {x, y}, u= f(es[mt[u]][0])) {
      if (v != root) std::swap(u, v);
      if (es[u][0] == x && es[u][1] == y) {
       w= u;
       break;
      }
     }
     for (int t= f(x); t != w; t= f(es[mt[t]][0])) idx[t]= ret, p[t]= w, que.push(t);
     for (int t= f(y); t != w; t= f(es[mt[t]][0])) idx[t]= ret, p[t]= w, que.push(t);
    } else if (idx[mt[y]] != ret) es[y]= {-1, -1}, es[mt[y]]= {x, -1}, idx[mt[y]]= ret, p[mt[y]]= y, que.push(mt[y]);
   }
  }
  return false;
 }
public:
 Matching(int n): n(n), ret(0), adj(n), mt(n, -1), idx(n, -1), p(n), es(n) {}
 void add_edge(int u, int v) { adj[u].push_back(v), adj[v].push_back(u); }
 std::pair<int, std::vector<int>> get_matching() {
  for (int i= 0; i < n; i++)
   if (mt[i] == -1) ret+= check(i);
  return std::make_pair(ret, mt);
 }
};
using namespace std;
namespace yukicoder421 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N, M;
 cin >> N >> M;
 vector<string> S(N);
 int bsize= 0, wsize= 0;
 for (int i= 0; i < N; i++) {
  cin >> S[i];
  for (int j= 0; j < M; j++) bsize+= S[i][j] == 'b', wsize+= S[i][j] == 'w';
 }
 Matching graph(N * M);
 int e= 0;
 for (int i= 0; i < N; i++) {
  for (int j= 0; j < M; j++)
   if ((i + j) & 1 && S[i][j] == 'b') {
    if (i > 0 && S[i - 1][j] == 'w') graph.add_edge(i * M + j, (i - 1) * M + j);
    if (i + 1 < N && S[i + 1][j] == 'w') graph.add_edge(i * M + j, (i + 1) * M + j);
    if (j > 0 && S[i][j - 1] == 'w') graph.add_edge(i * M + j, i * M + j - 1);
    if (j + 1 < M && S[i][j + 1] == 'w') graph.add_edge(i * M + j, i * M + j + 1);
   }
 }
 if (bsize > wsize) swap(bsize, wsize);
 int x= graph.get_matching().first;
 int ans= 100 * x + 10 * (bsize - x) + wsize - bsize;
 cout << ans << '\n';
 return 0;
}
}
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 yukicoder421::main();
 return 0;
}