結果

問題 No.421 しろくろチョコレート
ユーザー hashiryo
提出日時 2023-03-14 16:05:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 5,627 bytes
コンパイル時間 2,146 ms
コンパイル使用メモリ 211,984 KB
最終ジャッジ日時 2025-02-11 11:09:24
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0