結果

問題 No.421 しろくろチョコレート
コンテスト
ユーザー hashiryo
提出日時 2023-03-16 12:12:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 343 ms / 2,000 ms
コード長 10,992 bytes
コンパイル時間 3,404 ms
コンパイル使用メモリ 242,892 KB
最終ジャッジ日時 2025-02-11 11:50:26
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 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]; }
};
// sgn: + -> max, - -> min, 0 -> unweighted
template <std::int_least8_t sgn, class Matroid1, class Matroid2, class cost_t> std::vector<std::vector<int>> weighted_matroid_intersection(int n, Matroid1 M1, Matroid2 M2, std::vector<cost_t> c) {
 assert(n == (int)c.size());
 bool b[n];
 std::fill_n(b, n, false);
 std::vector<int> I[2], p;
 std::vector<std::vector<int>> ret(1);
 for (int u= 0; u < n; u++) I[0].push_back(u);
 if constexpr (sgn > 0) {
  auto cmx= *std::max_element(c.begin(), c.end());
  for (auto &x: c) x-= cmx;
 } else {
  auto cmi= *std::min_element(c.begin(), c.end());
  for (auto &x: c) x-= cmi;
 }
 for (auto &x: c) x*= sgn * (n + 1);
 for (bool converged= false; !converged;) {
  converged= true, M1.build(I[1]), M2.build(I[1]);
  std::priority_queue<std::pair<cost_t, int>> pq;
  std::vector<cost_t> dist(n, std::numeric_limits<cost_t>::lowest());
  for (int u: I[0])
   if (M1.oracle(u)) pq.emplace(dist[u]= c[u] - 1, u);
  for (p.assign(n, -1); pq.size();) {
   auto [d, u]= pq.top();
   if (pq.pop(); d != dist[u]) continue;
   if (b[u]) {
    for (int v: I[0])
     if (M1.oracle(u, v))
      if (cost_t cost= d + c[v] - 1; dist[v] < cost) pq.emplace(dist[v]= cost, v), p[v]= u;
   } else {
    if (M2.oracle(u)) {
     for (int v= u; v != -1; v= p[v]) b[v]= !b[v];
     I[0].clear(), I[1].clear(), converged= false;
     for (int u= 0; u < n; u++) I[b[u]].push_back(u);
     ret.emplace_back(I[1]);
     break;
    }
    for (int v: I[1])
     if (M2.oracle(v, u))
      if (cost_t cost= d - c[v] - 1; dist[v] < cost) pq.emplace(dist[v]= cost, v), p[v]= u;
   }
  }
 }
 return ret;
}
using namespace std;
namespace ALPC_E {
// https://atcoder.jp/contests/practice2/tasks/practice2_e
int main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N, K;
 cin >> N >> K;
 int M= N * N;
 std::vector<long long> w(M);
 std::vector<std::vector<int>> parts1(N), parts2(N);
 std::vector<int> r(N, K);
 auto edge_id= [N](int i, int j) { return i * N + j; };
 auto edge2ij= [N](int e) { return std::make_pair(e / N, e % N); };
 for (int i= 0; i < N; i++)
  for (int j= 0; j < N; j++) {
   int e= edge_id(i, j);
   cin >> w[e];
   parts1[i].push_back(e);
   parts2[j].push_back(e);
  }
 PartitionMatroid M1(M, parts1, r), M2(M, parts2, r);
 auto S= weighted_matroid_intersection<+1>(M, M1, M2, w);
 long long ans= 0;
 int mi= 0;
 for (int i= 1, ed= S.size(); i < ed; i++) {
  long long sum= 0;
  for (int e: S[i]) sum+= w[e];
  if (ans < sum) {
   ans= sum;
   mi= i;
  }
 }
 cout << ans << '\n';
 vector t(N, string(N, '.'));
 for (int e: S[mi]) {
  auto [i, j]= edge2ij(e);
  t[i][j]= 'X';
 }
 for (int i= 0; i < N; i++) cout << t[i] << '\n';
 return 0;
}
}  // namespace ALPC_E
namespace atcoder_geocon2013_b {
// https://atcoder.jp/contests/geocon2013/tasks/geocon2013_b
// |台集合| <= 2500
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N;
 cin >> N;
 long long X[N], Y[N];
 for (int i= 0; i < N; i++) {
  cin >> X[i] >> Y[i];
 }
 std::vector<std::vector<int>> partl(N), partr(N);
 std::vector<double> w;
 int e= 0;
 for (int i= 0; i < N; i++)
  for (int j= 0; j < N; j++) {
   if (i != j && X[i] * X[j] > 0) continue;
   double cost;
   if (i == j) cost= abs(X[i]);
   else {
    double xsum= X[i] + X[j], ydif= Y[i] - Y[j];
    cost= sqrt(xsum * xsum + ydif * ydif) / 2;
   }
   partl[i].push_back(e), partr[j].push_back(e), w.push_back(cost), ++e;
  }
 PartitionMatroid M1(e, partl, vector(N, 1)), M2(e, partr, vector(N, 1));
 auto S= weighted_matroid_intersection<-1>(e, M1, M2, w);
 double ans= 0;
 for (auto d: S[N]) ans+= w[d];
 printf("%.7lf\n", ans);
 return 0;
}
}
namespace AOJ2429 {
// https://onlinejudge.u-aizu.ac.jp/problems/2429
// |台集合| <= 1e4
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int n;
 cin >> n;
 int W[n][n], E[n][n];
 for (int i= 0; i < n; ++i)
  for (int j= 0; j < n; ++j) cin >> W[i][j];
 for (int i= 0; i < n; ++i)
  for (int j= 0; j < n; ++j) cin >> E[i][j];
 int m= n * n;
 vector<long long> w(m);
 vector<vector<int>> partl(n), partr(n);
 long long mincost= 0;
 string F[n];
 for (int i= 0; i < n; ++i) {
  cin >> F[i];
  int e= i * n;
  for (int j= 0; j < n; ++j, ++e) {
   partl[i].push_back(e), partr[j].push_back(e);
   if (F[i][j] == '.') w[e]= W[i][j];
   else w[e]= -E[i][j], mincost+= E[i][j];
  }
 }
 PartitionMatroid M1(m, partl, vector(n, 1)), M2(m, partr, vector(n, 1));
 auto S= weighted_matroid_intersection<-1>(m, M1, M2, w);
 bool write[n][n];
 for (int i= n; i--;)
  for (int j= n; j--;) write[i][j]= 0;
 for (auto d: S[n]) mincost+= w[d], write[d / n][d % n]= 1;
 cout << mincost << '\n';
 vector<tuple<int, int, string>> ans;
 for (int i= 0; i < n; ++i)
  for (int j= 0; j < n; ++j)
   if (write[i][j] ^ (F[i][j] != '.')) ans.emplace_back(i + 1, j + 1, write[i][j] ? "write" : "erase");
 cout << ans.size() << '\n';
 for (auto [R, C, operate]: ans) cout << R << " " << C << " " << operate << '\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= weighted_matroid_intersection<0>(e, M1, M2, vector(e, 1)).size() - 1;
 int ans= 100 * x + 10 * (bsize - x) + wsize - bsize;
 cout << ans << '\n';
 return 0;
}
}
// matroid_intersection
int main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 // ALPC_E::main();
 // atcoder_geocon2013_b::main();
 // AOJ2429::main();
 yukicoder421::main();
 return 0;
}
0