結果
| 問題 | No.421 しろくろチョコレート |
| ユーザー |
 hashiryo
|
| 提出日時 | 2023-03-13 20:28:41 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 92 ms / 2,000 ms |
| コード長 | 9,714 bytes |
| コンパイル時間 | 2,866 ms |
| コンパイル使用メモリ | 226,628 KB |
| 最終ジャッジ日時 | 2025-02-11 10:59:29 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 65 |
ソースコード
#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 debugMatrixtemplate<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 onusing 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/2128int 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/1163signed 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_Asigned 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;}