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

提出ソース

結果

問題	No.421 しろくろチョコレート
ユーザー	hashiryo
提出日時	2023-03-13 20:28:41
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	78 ms / 2,000 ms
コード長	9,714 bytes
コンパイル時間	3,526 ms
コンパイル使用メモリ	233,860 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-18 07:42:08
合計ジャッジ時間	5,466 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	9 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	5 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	7 ms 6,940 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	1 ms 6,940 KB
testcase_14	AC	1 ms 6,940 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	36 ms 6,940 KB
testcase_17	AC	25 ms 6,940 KB
testcase_18	AC	33 ms 6,940 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	AC	18 ms 6,940 KB
testcase_21	AC	24 ms 6,940 KB
testcase_22	AC	8 ms 6,944 KB
testcase_23	AC	1 ms 6,940 KB
testcase_24	AC	1 ms 6,940 KB
testcase_25	AC	2 ms 6,944 KB
testcase_26	AC	2 ms 6,944 KB
testcase_27	AC	1 ms 6,940 KB
testcase_28	AC	4 ms 6,940 KB
testcase_29	AC	6 ms 6,940 KB
testcase_30	AC	5 ms 6,940 KB
testcase_31	AC	16 ms 6,944 KB
testcase_32	AC	7 ms 6,940 KB
testcase_33	AC	9 ms 6,944 KB
testcase_34	AC	2 ms 6,940 KB
testcase_35	AC	2 ms 6,940 KB
testcase_36	AC	5 ms 6,940 KB
testcase_37	AC	29 ms 6,944 KB
testcase_38	AC	65 ms 6,944 KB
testcase_39	AC	3 ms 6,940 KB
testcase_40	AC	18 ms 6,944 KB
testcase_41	AC	2 ms 6,940 KB
testcase_42	AC	2 ms 6,944 KB
testcase_43	AC	3 ms 6,940 KB
testcase_44	AC	37 ms 6,940 KB
testcase_45	AC	2 ms 6,944 KB
testcase_46	AC	2 ms 6,940 KB
testcase_47	AC	5 ms 6,944 KB
testcase_48	AC	14 ms 6,940 KB
testcase_49	AC	3 ms 6,944 KB
testcase_50	AC	2 ms 6,940 KB
testcase_51	AC	32 ms 6,944 KB
testcase_52	AC	5 ms 6,940 KB
testcase_53	AC	2 ms 6,940 KB
testcase_54	AC	2 ms 6,940 KB
testcase_55	AC	2 ms 6,944 KB
testcase_56	AC	2 ms 6,944 KB
testcase_57	AC	3 ms 6,940 KB
testcase_58	AC	9 ms 6,940 KB
testcase_59	AC	4 ms 6,944 KB
testcase_60	AC	70 ms 6,944 KB
testcase_61	AC	78 ms 6,940 KB
testcase_62	AC	2 ms 6,940 KB
testcase_63	AC	2 ms 6,944 KB
testcase_64	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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

using namespace std;
template <typename Matroid1, typename Matroid2> std::vector<int> matroid_intersection(int n, Matroid1 M1, Matroid2 M2) {
 std::vector<int> b(n, false), pre(n), I[2];
 for (int e= 0; e < n; e++) I[0].push_back(e);
 M1.build(I[1]), M2.build(I[1]);
 for (bool converged= false; !converged;) {
  pre.assign(n, false);
  std::vector L(1, std::vector<int>());
  for (int u: I[0])
   if (M1.oracle(u)) pre[u]= true, L[0].push_back(u);
  int m= 0;
  for (; L.back().size(); m+= 2) {
   L.push_back({});
   for (int e: L[m]) {
    if (converged= M2.oracle(e)) break;
    for (int f: I[1])
     if (!pre[f] && M2.oracle(f, e)) L[m + 1].push_back(f), pre[f]= true;
   }
   if (converged) break;
   L.push_back({});
   for (int e: L[m + 1])
    for (int f: I[0])
     if (!pre[f] && M1.oracle(e, f)) L[m + 2].push_back(f), pre[f]= true;
  }
  if (!converged) break;
  std::vector<std::vector<int>> L2(m + 1);
  for (int e: L[m])
   if (M2.oracle(e)) L2[m].push_back(e);
  for (int i= m; i; i-= 2) {
   for (int e: L[i - 1])
    for (int f: L2[i])
     if (M1.oracle(e, f)) {
      L2[i - 1].push_back(e);
      break;
     }
   for (int e: L[i - 2])
    for (int f: L2[i - 1])
     if (M2.oracle(f, e)) {
      L2[i - 2].push_back(e);
      break;
     }
  }
  pre.assign(n, -1);
  for (int e: L2[0])
   if (M1.oracle(e)) {
    bool isok= false;
    if (m) {
     std::vector<size_t> ei(m);
     for (int i= 0; e != -1;) {
      if (ei[i] == L2[i + 1].size()) e= pre[e], ei[i--]= 0;
      else if (int f= L2[i + 1][ei[i]++]; pre[f] == -1 && (i & 1 ? M1.oracle(e, f) : M2.oracle(f, e)))
       if (pre[f]= e, e= f; ++i == m) {
        if (M2.oracle(e))
         for (isok= true; e != -1; e= pre[e]) b[e]= !b[e];
        else e= pre[e], --i;
       }
     }
    } else if (M2.oracle(e)) isok= true, b[e]= 1;
    if (isok) {
     converged= false, I[0].clear(), I[1].clear();
     for (int u= 0; u < n; u++) I[b[u]].push_back(u);
     M1.build(I[1]), M2.build(I[1]);
    }
   }
 }
 return I[1];
}
class GraphicMatroid {
 int n;
 std::vector<std::array<int, 2>> es;
 std::vector<int> g, pos, comp, in, out;
 inline bool is_ancestor(int u, int v) const { return in[u] <= in[v] && in[v] < out[u]; }
public:
 GraphicMatroid(int n_): n(n_), comp(n), in(n), out(n) {}
 void add_edge(int u, int v) { es.push_back({u, v}); }
 void build(const std::vector<int> &I) {
  in.assign(n, -1), g.resize(I.size() * 2), pos.assign(n + 1, 0);
  for (int e: I) {
   auto [u, v]= es[e];
   ++pos[u], ++pos[v];
  }
  for (int i= 0; i < n; ++i) pos[i + 1]+= pos[i];
  for (int e: I) {
   auto [u, v]= es[e];
   g[--pos[u]]= v, g[--pos[v]]= u;
  }
  std::vector<int> ei(pos.begin(), pos.begin() + n), pre(n, -1);
  for (int u= 0, t= 0, p; u < n; u++)
   if (in[u] == -1)
    for (in [comp[u]= p= u]= t++; p >= 0;) {
     if (ei[p] == pos[p + 1]) out[p]= t, p= pre[p];
     else if (int v= g[ei[p]++]; in[v] == -1) comp[v]= comp[u], pre[v]= p, in[p= v]= t++;
    }
 }
 inline bool oracle(int e) const { return comp[es[e][0]] != comp[es[e][1]]; }
 inline bool oracle(int e, int f) const {
  if (oracle(f)) return true;
  return e= es[e][in[es[e][0]] < in[es[e][1]]], is_ancestor(e, es[f][0]) != is_ancestor(e, es[f][1]);
 }
};
struct PartitionMatroid {
 std::vector<int> belong, R, cnt;
 PartitionMatroid(int m_, const std::vector<std::vector<int>> &parts, const std::vector<int> &R_): belong(m_, -1), R(R_) {
  assert(parts.size() == R.size());
  for (int i= parts.size(); i--;)
   for (int e: parts[i]) belong[e]= i;
 }
 void build(const std::vector<int> &I) {
  cnt= R;
  for (int e: I)
   if (belong[e] != -1) cnt[belong[e]]--;
 }
 inline bool oracle(int e) const { return belong[e] == -1 || cnt[belong[e]] > 0; }
 inline bool oracle(int e, int f) const { return oracle(f) || belong[e] == belong[f]; }
};
namespace beecrowd2128 {
// https://www.beecrowd.com.br/judge/en/problems/view/2128
int main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int n, m, k;
 for (int cnt= 1; cin >> n >> m >> k; cnt++) {
  cout << "Instancia " << cnt << '\n';
  GraphicMatroid M1(n);
  vector<vector<int>> parts(k);
  for (int i= 0; i < m; i++) {
   int u, v, c;
   cin >> u >> v >> c;
   M1.add_edge(--u, --v);
   parts[--c].push_back(i);
  }
  PartitionMatroid M2(m, parts, vector<int>(k, 1));
  auto S= matroid_intersection(m, M1, M2);
  cout << (S.size() == n - 1 ? "sim" : "nao") << "\n\n";
 }
 return 0;
}
}
namespace AOJ1163 {
// https://onlinejudge.u-aizu.ac.jp/problems/1163
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 for (int m, n; cin >> m >> n && m;) {
  int b[m], r[n];
  for (int i= 0; i < m; ++i) cin >> b[i];
  for (int i= 0; i < n; ++i) cin >> r[i];
  vector<vector<int>> partl(m), partr(n);
  int e= 0;
  for (int i= 0; i < m; ++i)
   for (int j= 0; j < n; ++j)
    if (gcd(b[i], r[j]) > 1) partl[i].push_back(e), partr[j].push_back(e), ++e;
  PartitionMatroid M1(e, partl, vector(m, 1)), M2(e, partr, vector(n, 1));
  auto S= matroid_intersection(e, M1, M2);
  cout << S.size() << '\n';
 }
 return 0;
}
}
namespace AOJ_GRL7A {
// https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/7/GRL_7_A
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int L, R, M;
 cin >> L >> R >> M;
 vector<vector<int>> partl(L), partr(R);
 for (int i= 0; i < M; i++) {
  int a, b;
  cin >> a >> b;
  partl[a].push_back(i), partr[b].push_back(i);
 }
 PartitionMatroid M1(M, partl, vector(L, 1)), M2(M, partr, vector(R, 1));
 auto S= matroid_intersection(M, M1, M2);
 cout << S.size() << '\n';
 return 0;
}
}
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';
 }
 vector<vector<int>> partl(N * M), partr(N * M);
 int e= 0;
 auto add_edge= [&](int l, int r) { partl[l].push_back(e), partr[r].push_back(e), ++e; };
 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') add_edge(i * M + j, (i - 1) * M + j);
    if (i + 1 < N && S[i + 1][j] == 'w') add_edge(i * M + j, (i + 1) * M + j);
    if (j > 0 && S[i][j - 1] == 'w') add_edge(i * M + j, i * M + j - 1);
    if (j + 1 < M && S[i][j + 1] == 'w') add_edge(i * M + j, i * M + j + 1);
   }
 }
 if (bsize > wsize) swap(bsize, wsize);
 PartitionMatroid M1(e, partl, vector(N * M, 1)), M2(e, partr, vector(N * M, 1));
 int x= matroid_intersection(e, M1, M2).size();
 int ans= 100 * x + 10 * (bsize - x) + wsize - bsize;
 cout << ans << '\n';
 return 0;
}
}
int main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 // beecrowd2128::main();
 // AOJ1163::main();
 // AOJ_GRL7A::main();
 yukicoder421::main();
 return 0;
}