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

提出ソース

結果

問題	No.421 しろくろチョコレート
ユーザー	Min_25
提出日時	2016-10-30 12:47:32
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	3 ms / 2,000 ms
コード長	5,029 bytes
コンパイル時間	1,605 ms
コンパイル使用メモリ	111,264 KB
実行使用メモリ	4,348 KB
最終ジャッジ日時	2023-10-24 14:53:27
合計ジャッジ時間	3,293 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	2 ms 4,348 KB
testcase_05	AC	2 ms 4,348 KB
testcase_06	AC	2 ms 4,348 KB
testcase_07	AC	2 ms 4,348 KB
testcase_08	AC	2 ms 4,348 KB
testcase_09	AC	2 ms 4,348 KB
testcase_10	AC	2 ms 4,348 KB
testcase_11	AC	2 ms 4,348 KB
testcase_12	AC	2 ms 4,348 KB
testcase_13	AC	1 ms 4,348 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	2 ms 4,348 KB
testcase_18	AC	2 ms 4,348 KB
testcase_19	AC	2 ms 4,348 KB
testcase_20	AC	2 ms 4,348 KB
testcase_21	AC	2 ms 4,348 KB
testcase_22	AC	2 ms 4,348 KB
testcase_23	AC	2 ms 4,348 KB
testcase_24	AC	2 ms 4,348 KB
testcase_25	AC	2 ms 4,348 KB
testcase_26	AC	2 ms 4,348 KB
testcase_27	AC	2 ms 4,348 KB
testcase_28	AC	2 ms 4,348 KB
testcase_29	AC	2 ms 4,348 KB
testcase_30	AC	2 ms 4,348 KB
testcase_31	AC	2 ms 4,348 KB
testcase_32	AC	2 ms 4,348 KB
testcase_33	AC	2 ms 4,348 KB
testcase_34	AC	2 ms 4,348 KB
testcase_35	AC	2 ms 4,348 KB
testcase_36	AC	2 ms 4,348 KB
testcase_37	AC	2 ms 4,348 KB
testcase_38	AC	2 ms 4,348 KB
testcase_39	AC	2 ms 4,348 KB
testcase_40	AC	2 ms 4,348 KB
testcase_41	AC	2 ms 4,348 KB
testcase_42	AC	2 ms 4,348 KB
testcase_43	AC	2 ms 4,348 KB
testcase_44	AC	2 ms 4,348 KB
testcase_45	AC	2 ms 4,348 KB
testcase_46	AC	2 ms 4,348 KB
testcase_47	AC	2 ms 4,348 KB
testcase_48	AC	2 ms 4,348 KB
testcase_49	AC	2 ms 4,348 KB
testcase_50	AC	2 ms 4,348 KB
testcase_51	AC	3 ms 4,348 KB
testcase_52	AC	2 ms 4,348 KB
testcase_53	AC	2 ms 4,348 KB
testcase_54	AC	2 ms 4,348 KB
testcase_55	AC	2 ms 4,348 KB
testcase_56	AC	2 ms 4,348 KB
testcase_57	AC	2 ms 4,348 KB
testcase_58	AC	2 ms 4,348 KB
testcase_59	AC	2 ms 4,348 KB
testcase_60	AC	2 ms 4,348 KB
testcase_61	AC	2 ms 4,348 KB
testcase_62	AC	2 ms 4,348 KB
testcase_63	AC	2 ms 4,348 KB
testcase_64	AC	2 ms 4,348 KB

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

ソースコード

raw source code

#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);
}

yukicoder

結果

テストケース

ソースコード