結果

問題 No.459 C-VS for yukicoder
ユーザー hashiryohashiryo
提出日時 2021-12-16 14:46:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 63 ms / 2,000 ms
コード長 6,494 bytes
コンパイル時間 2,656 ms
コンパイル使用メモリ 219,368 KB
実行使用メモリ 16,336 KB
最終ジャッジ日時 2023-10-11 12:36:05
合計ジャッジ時間 7,286 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 2 ms
4,352 KB
testcase_03 AC 1 ms
4,348 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 1 ms
4,352 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 1 ms
4,352 KB
testcase_08 AC 2 ms
4,352 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,352 KB
testcase_11 AC 2 ms
4,352 KB
testcase_12 AC 1 ms
4,348 KB
testcase_13 AC 2 ms
4,352 KB
testcase_14 AC 2 ms
4,348 KB
testcase_15 AC 2 ms
4,348 KB
testcase_16 AC 2 ms
4,348 KB
testcase_17 AC 1 ms
4,356 KB
testcase_18 AC 2 ms
4,352 KB
testcase_19 AC 2 ms
4,352 KB
testcase_20 AC 2 ms
4,348 KB
testcase_21 AC 54 ms
16,336 KB
testcase_22 AC 26 ms
13,328 KB
testcase_23 AC 63 ms
14,124 KB
testcase_24 AC 20 ms
9,412 KB
testcase_25 AC 9 ms
6,288 KB
testcase_26 AC 5 ms
4,540 KB
testcase_27 AC 5 ms
4,612 KB
testcase_28 AC 9 ms
6,076 KB
testcase_29 AC 10 ms
6,540 KB
testcase_30 AC 5 ms
4,544 KB
testcase_31 AC 9 ms
5,648 KB
testcase_32 AC 3 ms
4,348 KB
testcase_33 AC 12 ms
6,368 KB
testcase_34 AC 12 ms
6,600 KB
testcase_35 AC 3 ms
4,352 KB
testcase_36 AC 9 ms
5,876 KB
testcase_37 AC 2 ms
4,348 KB
testcase_38 AC 12 ms
6,280 KB
testcase_39 AC 3 ms
4,348 KB
testcase_40 AC 8 ms
5,328 KB
testcase_41 AC 2 ms
4,352 KB
testcase_42 AC 7 ms
4,972 KB
testcase_43 AC 10 ms
6,044 KB
testcase_44 AC 4 ms
4,348 KB
testcase_45 AC 3 ms
4,352 KB
testcase_46 AC 3 ms
4,348 KB
testcase_47 AC 2 ms
4,352 KB
testcase_48 AC 10 ms
6,252 KB
testcase_49 AC 3 ms
4,348 KB
testcase_50 AC 11 ms
6,080 KB
testcase_51 AC 3 ms
4,348 KB
testcase_52 AC 5 ms
4,688 KB
testcase_53 AC 3 ms
4,348 KB
testcase_54 AC 12 ms
6,288 KB
testcase_55 AC 4 ms
4,348 KB
testcase_56 AC 7 ms
5,172 KB
testcase_57 AC 2 ms
4,348 KB
testcase_58 AC 12 ms
6,512 KB
testcase_59 AC 4 ms
4,352 KB
testcase_60 AC 5 ms
4,660 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define debugArray(x, n)                                      \
  cerr << __LINE__ << ": " << #x << " = {";                   \
  for (long long hoge = 0; (hoge) < (long long)(n); ++(hoge)) \
    cerr << ((hoge) ? "," : "") << x[hoge];                   \
  cerr << "}" << '\n'
#define debugMatrix(x, h, w)                                         \
  cerr << __LINE__ << ": " << #x << " =\n";                          \
  for (long long hoge = 0; (hoge) < (long long)(h); ++(hoge)) {      \
    cerr << ((hoge ? " {" : "{{"));                                  \
    for (long long fuga = 0; (fuga) < (long long)(w); ++(fuga))      \
      cerr << ((fuga ? ", " : "")) << x[hoge][fuga];                 \
    cerr << "}" << (hoge + 1 == (long long)(h) ? "}" : ",") << '\n'; \
  }
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#define debugMatrix(x, h, w) (void(0))
#endif

template <typename FlowAlgo>
class MaxFlowLowerBound : public FlowAlgo {
  using Edge = typename FlowAlgo::Edge;
  using flow_t = decltype(Edge::cap);
  std::vector<flow_t> in;
  int add_edge(int src, int dst, flow_t cap) {
    int e = this->adj[src].size();
    int re = src == dst ? e + 1 : this->adj[dst].size();
    this->adj[src].push_back(Edge{dst, re, cap});
    this->adj[dst].push_back(Edge{src, e, 0});
    return this->m++, re;
  }

 public:
  MaxFlowLowerBound(std::size_t n = 0) : FlowAlgo(n + 2), in(n) {}
  int add_vertex() {
    return this->adj.resize(++this->n), in.resize(this->n - 2, 0), this->n - 3;
  }
  std::vector<int> add_vertices(const std::size_t size) {
    std::vector<int> ret(size);
    std::iota(ret.begin(), ret.end(), this->n - 2);
    return this->adj.resize(this->n += size), in.resize(this->n - 2, 0), ret;
  }
  struct EdgePtr {
    friend class MaxFlowLowerBound;
    MaxFlowLowerBound *instance;
    int v, e;
    flow_t u;
    Edge &edge() { return instance->adj[v][e]; }
    Edge &rev() {
      Edge &e = edge();
      return instance->adj[e.dst][e.rev];
    }
    EdgePtr(MaxFlowLowerBound *instance, int v, int e, flow_t u)
        : instance(instance), v(v), e(e), u(u) {}

   public:
    EdgePtr() = default;
    int src() { return v; }
    int dst() { return edge().dst; }
    flow_t flow() { return u - edge().cap; }
    flow_t lower() { return flow() - rev().cap; }
    flow_t upper() { return u; }
  };
  EdgePtr add_edge(int src, int dst, flow_t lower, flow_t upper) {
    assert(lower <= upper);
    src += 2, dst += 2;
    assert(0 <= src && src < this->n);
    assert(0 <= dst && dst < this->n);
    this->m++;
    int e = this->adj[src].size();
    int re = src == dst ? e + 1 : this->adj[dst].size();
    if (lower * upper <= 0) {
      this->adj[src].push_back(Edge{dst, re, upper});
      this->adj[dst].push_back(Edge{src, e, -lower});
    } else if (lower > 0) {
      in[src - 2] -= lower, in[dst - 2] += lower;
      this->adj[src].push_back(Edge{dst, re, upper - lower});
      this->adj[dst].push_back(Edge{src, e, 0});
    } else {
      in[src - 2] -= upper, in[dst - 2] += upper;
      this->adj[src].push_back(Edge{dst, re, 0});
      this->adj[dst].push_back(Edge{src, e, upper - lower});
    }
    return EdgePtr(this, src, e, upper);
  }
  flow_t maxflow(int s, int t) {
    static constexpr flow_t INF = std::numeric_limits<flow_t>::max();
    flow_t sum = 0;
    for (int i = this->n - 2; i--;) {
      if (in[i] > 0) add_edge(0, i + 2, in[i]), sum += in[i];
      if (in[i] < 0) add_edge(i + 2, 1, -in[i]);
    }
    int re = add_edge(t += 2, s += 2, INF);
    if (this->flow(0, 1, INF) < sum) return -1;  // no solution
    return this->flow(s, t, INF) + this->adj[s][re].cap;
  }
};

template <class flow_t>
struct Dinic {
  Dinic(std::size_t _n = 0) : n(_n), m(0), adj(n) {}

 protected:
  struct Edge {
    int dst, rev;
    flow_t cap;
  };
  int n, m;
  std::vector<std::vector<Edge>> adj;
  std::vector<int> level, iter;
  inline void levelize(const int &s, const int &t) {
    level.assign(n, -1), level[s] = 0;
    std::queue<int> que;
    for (que.push(s); !que.empty();) {
      int u = que.front();
      que.pop();
      for (auto &e : adj[u])
        if (e.cap > 0 && level[e.dst] < 0) {
          level[e.dst] = level[u] + 1;
          if (e.dst == t) return;
          que.push(e.dst);
        }
    }
  }
  inline flow_t dfs(int u, const int &s, flow_t cur) {
    if (u == s) return cur;
    flow_t ret = 0;
    for (int &i = iter[u]; i < adj[u].size(); i++) {
      Edge &e = adj[u][i], &re = adj[e.dst][e.rev];
      if (level[u] <= level[e.dst] || re.cap == 0) continue;
      flow_t f = dfs(e.dst, s, std::min(cur - ret, re.cap));
      if (f <= 0) continue;
      e.cap += f, re.cap -= f, ret += f;
      if (ret == cur) return ret;
    }
    return level[u] = n, ret;
  }
  flow_t flow(int s, int t, flow_t flow_lim) {
    assert(0 <= s && s < n);
    assert(0 <= t && t < n);
    assert(s != t);
    flow_t ret = 0;
    for (flow_t f; ret < flow_lim; ret += f) {
      if (levelize(s, t), level[t] == -1) break;
      iter.assign(n, 0);
      if (!(f = dfs(t, s, flow_lim - ret))) break;
    }
    return ret;
  }
};

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin.tie(0);
  ios::sync_with_stdio(false);
  int H, W, N;
  cin >> H >> W >> N;
  int height[W] = {0};
  for (int i = 0; i < H; i++) {
    string S;
    cin >> S;
    for (int j = 0; j < W; j++) height[j] += S[j] == '#';
  }
  using MF = MaxFlowLowerBound<Dinic<long long>>;
  MF graph;
  MF::EdgePtr e[N][3];
  int s = graph.add_vertex(), t = graph.add_vertex();
  auto p = graph.add_vertices(N), q = graph.add_vertices(W);
  for (int i = 0; i < N; i++) {
    int C;
    cin >> C;
    graph.add_edge(s, p[i], 1, 9);
    for (int j = 0; j < 3; j++) e[i][j] = graph.add_edge(p[i], q[C + j], 0, 3);
  }
  for (int i = 0; i < W; i++) graph.add_edge(q[i], t, height[i], height[i]);
  graph.maxflow(s, t);
  for (int i = 0; i < N; i++) {
    string ans[3] = {"...", "...", "..."};
    for (int j = 0; j < 3; j++) {
      auto f = e[i][j].flow();
      for (int k = 0; k < f; k++) ans[k][j] = '#';
    }
    for (int j = 0; j < 3; j++) cout << ans[j] << '\n';
  }
  return 0;
  return 0;
}
0