結果

問題 No.421 しろくろチョコレート
ユーザー Min_25
提出日時 2016-10-30 12:47:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 5,029 bytes
コンパイル時間 1,780 ms
コンパイル使用メモリ 111,024 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-23 07:14:47
合計ジャッジ時間 3,461 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

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

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <stack>
#include <queue>
#include <tuple>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define _rep(_1, _2, _3, _4, name, ...) name
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))
#define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)
using namespace std;
using i8 = signed char;
using i16 = signed short;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f80 = long double;
class MaximumMatching {
  // Note: each vertex is 1-indexed.
public:
  struct edge {
    int from, to;
  };
  MaximumMatching(int N, const vector<edge>& raw_edges) : N(N) {
    offsets.assign(N + 2, 0);
    for (auto& e : raw_edges) {
      offsets[e.from + 1] += 1;
      offsets[e.to + 1] += 1;
    }
    rep(i, N + 1) offsets[i + 1] += offsets[i];
    edges.resize(2 * raw_edges.size());
    for (auto& e : raw_edges) {
      edges[offsets[e.from]++] = {e.from, e.to};
      edges[offsets[e.to]++] = {e.to, e.from};
    }
    rep(i, N + 1) offsets[N + 1 - i] = offsets[N - i];
    offsets[0] = 0;
  }
  int maximum_matching() {
    vector<int> label(N + 1, -1), mate(N + 1, 0), first(N + 1, 0);
    vector<int> que(N);
    int qh = 0, qt = 0;
    auto enqueue = [&] (int v) { que[qt++] = v; };
    auto dequeue = [&] { return que[qh++]; };
    auto encode = [&] (int eid) { return (N + 1) + eid; };
    auto decode = [&] (int h) { return h - (N + 1); };
    function< int(int) > find_first = [&] (int v) {
      return label[first[v]] < 0 ? first[v] : first[v] = find_first(first[v]);
    };
    function< void(int, int) > rematch = [&] (int v, int w) {
      auto t = mate[v]; mate[v] = w;
      if (mate[t] != v) return;
      if (label[v] <= N) {
        mate[t] = label[v];
        rematch(label[v], t);
      } else {
        auto& e = edges[decode(label[v])];
        int x = e.from, y = e.to;
        rematch(x, y); rematch(y, x);
      }
    };
    auto contract = [&] (int x, int y, int eid) {
      int r = find_first(x), s = find_first(y);
      if (r == s) return;
      auto h = encode(eid);
      label[r] = label[s] = -h;
      int join = -1; // lca
      while (1) {
        if (s != 0) swap(r, s);
        r = find_first(label[mate[r]]);
        if (label[r] == -h) {
          join = r;
          break;
        } else label[r] = -h;
      }
      for (auto v : { first[x], first[y] }) {
        for (; v != join; v = first[label[mate[v]]]) {
          label[v] = h;
          first[v] = join;
          enqueue(v);
        }
      }
    };
    auto augment = [&] (int u) {
      label[u] = first[u] = 0;
      for (qh = qt = 0, que[qt++] = u; qh < qt; ) {
        auto x = dequeue();
        rep(eid, offsets[x], offsets[x + 1]) {
          auto y = edges[eid].to;
          if (mate[y] == 0 && y != u) {
            mate[y] = x;
            rematch(x, y);
            return true;
          } else if (label[y] >= 0) {
            contract(x, y, eid);
          } else if (label[mate[y]] < 0) {
            label[mate[y]] = x;
            first[mate[y]] = y;
            enqueue(mate[y]);
          }
        }
      }
      return false;
    };
    int matching = 0;
    rep(u, 1, N + 1) if (mate[u] == 0 && augment(u)) {
      matching += 1;
      if (N - 2 * matching <= 1) break;
      if (10 * qt < N) {
        label[0] = -1;
        rep(qi, qt) label[que[qi]] = label[mate[que[qi]]] = -1;
      } else fill(label.begin(), label.end(), -1);
    }
    /*
    vector< pair<int, int> > matchings(matching);
    matching = 0;
    rep(u, 1, N + 1) if (mate[u] > u) {
      matchings[matching++] = {u, mate[u]};
    }
    */
    return matching;
  }
private:
  int N;
  vector<int> offsets;
  vector<edge> edges;
};
void solve() {
  static char B[64][64];
  int H, W;
  while (~scanf("%d %d", &H, &W)) {
    rep(y, H) scanf("%s", B[y]);
    vector<MaximumMatching::edge> edges; edges.reserve(2 * H * W);
    auto encode = [&] (int x, int y) {
      return y * W + x + 1;
    };
    int counts[2] = {};
    rep(y, H) rep(x, W) if (B[y][x] != '.') {
      counts[(x + y) & 1] += 1;
      if (x + 1 < W && B[y][x + 1] != '.') {
        edges.push_back({encode(x, y), encode(x + 1, y)});
      }
      if (y + 1 < H && B[y + 1][x] != '.') {
        edges.push_back({encode(x, y), encode(x, y + 1)});
      }
    }
    auto mm = MaximumMatching(H * W, edges).maximum_matching();
    auto mc = min(counts[0], counts[1]);
    auto ans = 100 * mm + 10 * (mc - mm) + 1 * (counts[0] + counts[1] - 2 * mc);
    printf("%d\n", ans);
  }
}
int main() {
  clock_t beg = clock();
  solve();
  clock_t end = clock();
  fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0