제출 #685355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
685355		lunchbox1	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	378 ms	262144 KiB

dango_maker

// #include <algorithm>
// #include <array>
// #include <iostream>
// #include <vector>
// #include <queue>
// #include <numeric>
#include <bits/stdc++.h>
using namespace std;

const int N = 3000;

#define assert(...) 0

// https://judge.yosupo.jp/submission/110301

struct BipartiteGraph{ // https://judge.yosupo.jp/submission/59969
  // Max matching in O(E root(V)) --> considerably fast, runs under 100ms for E, V <= 2e5 on library checker
private:
    int n;
    int Lpart, Rpart;
    int matching_num;
    // std::vector<std::vector<int>> G;
    vector<array<int, 2>> raw_edges;
    vector<int> num_starts, final_edges;

public:
    std::vector<int> match;

    BipartiteGraph(int a, int b, int p = 0): Lpart(a), Rpart(b), n(a + b), matching_num(-1), num_starts(a + b + 1, 0), match(n, -1) {
      raw_edges.reserve(p);
    }
    BipartiteGraph(int a, int b, const vector<array<int, 2>>& Edges): Lpart(a), Rpart(b), n(a + b), matching_num(-1), raw_edges(Edges), num_starts(a + b + 1, 0), match(n, -1) {}

    inline void addEdge(int u, int v){ raw_edges.push_back({u, v});}

    inline void build() {
      for(const auto& [u, v]: raw_edges) {
        ++num_starts[u + 1];
        ++num_starts[v + Lpart + 1];
      }
      for(int i = 1; i <= n; ++i) num_starts[i] += num_starts[i - 1];
      final_edges.resize(num_starts[n]);
      vector<int> start(num_starts.begin(), num_starts.begin() + n);

      for(const auto& [u, v]: raw_edges){
        final_edges[start[u]++] = v + Lpart;
        final_edges[start[v + Lpart]++] = u;
      }

    }
    int maxMatching(){
      if (final_edges.size() != raw_edges.size()) build();

        int res = 0; bool update = true;
        std::vector<int> pre(Lpart, -1), root(Lpart, -1);
        while(update){
            update = false; std::queue<int> que;
            for(int i = 0; i < Lpart; i++){
                if(!~match[i]){
                    root[i] = i; que.push(i);
                }
            }
            while(que.size()){
                int v = que.front(); que.pop();
                if(~match[root[v]]) continue;
                for(int cur = num_starts[v]; cur < num_starts[v + 1]; ++cur){
                  int nv = final_edges[cur];
                    if(!~match[nv]){
                        while(~nv){
                            match[nv] = v; std::swap(match[v], nv); v = pre[v];
                        }
                        update = true; ++res;
                        break;
                    }
                    nv = match[nv];
                    if(~pre[nv]) continue;
                    pre[nv] = v, root[nv] = root[v];
                    que.push(nv);
                }
            }
            if(update){
                std::fill(pre.begin(), pre.end(), -1);
                std::fill(root.begin(), root.end(), -1);
            }
        }
        return matching_num = res;
    }

    std::vector<std::array<int, 2>> maxMatchingEdges() {
      if (matching_num == -1)
        maxMatching();
      std::vector<std::array<int, 2>> ans; ans.reserve(matching_num);

      for(int i = 0; i < Lpart; ++i){
        if (match[i] != -1)
          ans.push_back({i, match[i] - Lpart});
      }
      return ans;
    }


    inline int pair(int u) const {return match[u];}

    std::vector<std::array<int, 2>> minimumEdgeCover(){ // Minimum edges to cover each vertex atleast once.
        if (matching_num == -1)
          maxMatching();
        int idx = 0;
        std::vector<std::array<int, 2>> res(n - matching_num);
        for(int i = 0; i < Lpart; i++){
            if(match[i] != -1) res[idx++] = {i, match[i]};
            else res[idx++] = {i, final_edges[num_starts[i + 1] - 1]};
        }
        assert(n - matching_num == idx);
        return res;
    }

    std::pair<std::vector<int>, std::vector<int>> minimumVertexCover(){
        if (matching_num == -1)
          maxMatching();
        std::vector<bool> reachable(n);
        for(int i = 0; i < Lpart; i++){
            if(match[i] != -1) continue;
            std::queue<int> que;
            que.push(i);
            while(que.size()){
                int v = que.front(); que.pop();
                reachable[v] = true;
                for(int cur = num_starts[v]; cur < num_starts[v + 1]; ++cur){
                  const int nv = final_edges[cur];
                    if(reachable[nv]) continue;
                    if(v >= Lpart && match[v] == nv){
                        reachable[nv] = true;
                        que.push(nv);
                    }
                    if(v < Lpart && match[v] != nv){
                        reachable[nv] = true;
                        que.push(nv);
                    }
                }
            }
        } 
        std::vector<int> left, right;
        for(int i = 0; i < n; i++){
            if(i < Lpart && !reachable[i]) left.emplace_back(i);
            if(i >= Lpart && reachable[i]) right.emplace_back(i);
        }  
        return std::make_pair(left, right);
    }   

    std::pair<std::vector<int>, std::vector<int>> maxIndependentSet(){
        if (matching_num == -1)
          maxMatching();

        std::vector<int> left, right;
        auto p = minimumVertexCover();
        std::vector<bool> complement(n, false);
        for(const int &v : p.first) complement[v] = true;
        for(const int &v : p.second) complement[v] = true;
        for(int i = 0; i < n; i++){
            if(complement[i]) continue;
            if(i < Lpart) right.emplace_back(i);
            else left.emplace_back(i);
        }
        return std::make_pair(left, right);
    }
};




struct BipartiteEdgeColoring {
  struct UnionFind {
    vector<int> UF; UnionFind(int N) : UF(N, -1) {}
    inline int find(int v) { return UF[v] < 0 ? v : UF[v] = find(UF[v]); }
    inline void join(int v, int w) {
    if ((v = find(v)) == (w = find(w))) return;
    if (UF[v] > UF[w]) swap(v, w);
    UF[v] += UF[w]; UF[w] = v; return;}
  };

  struct Pair {
    int s, v; Pair(int s, int v) : s(s), v(v) {}
    bool operator < (const Pair &o) const { return s > o.s; }
  };
  int makeDRegular(int &V, vector<pair<int, int>> &edges, int &L) { // O(V log V + E), adds atmost E + D new edges
    vector<int> deg(V, 0); 
    for (auto &&e : edges) {
      deg[e.first]++; deg[e.second]++;
    }
    int D = *max_element(deg.begin(), deg.end()); UnionFind uf(V);
    vector<int> cnt(2, 0);
    int R = V - L;
    for (int s = 0; s < 2; s++) {
      std::priority_queue<Pair> PQ;
        for(int v = s * L; v < L + s * R; ++v) {
          PQ.push({deg[v], v});
        }
    cnt[s] = PQ.size();
    while (int(PQ.size()) >= 2) {
      Pair a = PQ.top(); PQ.pop(); Pair b = PQ.top(); PQ.pop();
      if (a.s + b.s <= D) { uf.join(a.v, b.v); PQ.emplace(a.s + b.s, a.v); --cnt[s];}
      else break;
    }
    }
    vector<int> id(V, -1); 
    if (cnt[0] >= cnt[1]) {
      int curId = 0;
      for(int v = 0;  v < V; ++v)
        if (uf.find(v) == v)
          id[v] = curId++;
    }
    else{
      int curId = 0;
      for(int v = V - 1;  v >= 0; --v)
        if (uf.find(v) == v)
          id[v] = curId++;
      for(auto &&e: edges){
        swap(e.first, e.second);
      }
      swap(cnt[0], cnt[1]);
    }
    assert (cnt[0] >= cnt[1]);
    deg.assign(V = cnt[0] * 2, 0); edges.reserve(V * D / 2);

    for (auto &&e : edges) {
      deg[e.first = id[uf.find(e.first)]]++;
      deg[e.second = id[uf.find(e.second)]]++;
      assert (e.first < e.second);
    }

    for(int v = 0, w = cnt[0]; v < cnt[0]; ++v) {
      while (deg[v] < D){
        while (w < V && deg[w] == D) ++w;
        int x = min(D - deg[w], D - deg[v]);
        for(int k = 0; k < x; ++k){
          edges.emplace_back(v, w);
        }
        deg[v] += x;
        deg[w] += x;
      }
    }
    L = cnt[0];
    return D;
  }
  vector<int> eulerianCircuit(
      int V, const vector<pair<int, int>> &edges, const vector<int> &inds) {
    vector<vector<pair<int, int>>> G(V); vector<int> circuit;
    for (int i = 0; i < int(inds.size()); i++) {
      int v, w; tie(v, w) = edges[inds[i]];
      G[v].emplace_back(w, i); G[w].emplace_back(v, i);
    }
    vector<bool> vis1(V, false), vis2(inds.size(), false);
    vector<pair<int, int>> stk; for (int s = 0; s < V; s++) if (!vis1[s]) {
      stk.clear(); stk.emplace_back(s, -1); while (!stk.empty()) {
        int v, w, e; tie(v, e) = stk.back(); vis1[v] = true;
        if (G[v].empty()) { circuit.emplace_back(e); stk.pop_back(); }
        else {
          tie(w, e) = G[v].back(); G[v].pop_back();
          if (!vis2[e]) { vis2[e] = true; stk.emplace_back(w, e); }
        }
      }
      circuit.pop_back();
    }
    for (auto &&e : circuit) e = inds[e];
    return circuit;
  }
  vector<int> color;

  // static vector<int> maxMatchDRegular(int V, vector<pair<int, int>> edges, int D, int K) {
  //  const int E = edges.size();
  //  const int L = (V >> 1);
  //  assert (E == ((V * 1LL * D) / 2) && K <= D && (L << 1) == V);
  //  vector<int> color(E, -1);

  //  vector<vector<int>> G(V);

  //  vector<int> xv(E);
  //  for(int i = 0; i < E; ++i) {
  //    int u, v; tie(u, v) = edges[i];
  //    G[u].push_back(i);
  //    xv[i] = u ^ v;
  //  }

  //  vector<int> match(V, -1);
  //  vector<int> path;

  //  function<bool(int, int)> augment = [&] (int u, int b) {
  //    if (u > L) {
  //      if (match[u] == -1){
  //        return true;
  //      }
  //      u = edges[match[u]].second;
  //      path.push_back(match[u]);

  //      int k = G
  //    }
  //    else{
  //      int v = G[u].size();
  //      int x = random_long(0, v - 1);
  //      path.push_back()
  //    }

  //  };

  //  for(int i = 0; i < K; ++i) {

  //  }
  // }

  BipartiteEdgeColoring(int L, int R, vector<pair<int, int>> edges) // O(E sqrt V log (D))
      : color(edges.size(), -1) {
     int V = L + R;
    for (auto &&e : edges) {
      assert(e.first < L && e.second < R);
      e.second += L;
    }

    int D = makeDRegular(V, edges, L), curCol = 0;

    for(auto &&e: edges){
      assert (e.first < L && e.second >= L);
    }
    R = L;
    function<void(int, const vector<int> &)> rec = [&] ( 
        int d, const vector<int> &inds) {
      if (d == 0) return;
      else if (d == 1) {
        for (int e : inds) if (e < int(color.size())) color[e] = curCol;
        curCol++;
      } else if (d % 2 == 0) {
        vector<int> circuit = eulerianCircuit(V, edges, inds), half1, half2;
        half1.reserve(circuit.size() / 2); half2.reserve(circuit.size() / 2);
        for (int i = 0; i < int(circuit.size()); i += 2) {
          half1.push_back(circuit[i]); half2.push_back(circuit[i + 1]);
        }
        rec(d / 2, half1); rec(d / 2, half2);
      } else {


        vector<vector<int>> G(V); 

        BipartiteGraph mm(L, L);

        for (int e : inds) {
          int v, w; tie(v, w) = edges[e]; 
          mm.addEdge(v, w - L);
        }
        mm.maxMatching();
        vector<int> unmatched;
        for (int e : inds) {
          int v, w; tie(v, w) = edges[e]; 
          if (mm.match[v] == w) {
            mm.match[v] = -1; 
            mm.match[w] = -1;
            if (e < int(color.size())) color[e] = curCol;
          } else unmatched.push_back(e);
        }
        curCol++; rec(d - 1, unmatched);
      }
    };
    vector<int> inds(edges.size()); iota(inds.begin(), inds.end(), 0);
    rec(D, inds);
  }
};

int n, m;
string s[N];

bool t1(int i, int j) {
  return i > 0 && i < n - 1 && s[i - 1][j] == 'R' && s[i][j] == 'G' && s[i + 1][j] == 'W';
}

bool t2(int i, int j) {
  return j > 0 && j < m - 1 && s[i][j - 1] == 'R' && s[i][j] == 'G' && s[i][j + 1] == 'W';
}

int iu[N][N], iv[N][N], u = 0, v = 0;
vector<pair<int, int>> edge;



void link_(int i1, int j1, int i2, int j2) {
  if (i1 < 0 || i1 >= n || i2 < 0 || i2 >= n || j1 < 0 || j1 >= m || j2 < 0 || j2 >= m)
    return;
  if (iu[i1][j1] != -1 && iv[i2][j2] != -1) {
    // cout << i1 << ' ' << j1 << " -> " << i2 << ' ' << j2 << '\n';
    edge.push_back({iu[i1][j1], iv[i2][j2]});
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    cin >> s[i];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      iu[i][j] = t1(i, j) ? u++ : -1;
      iv[i][j] = t2(i, j) ? v++ : -1;
    }
  // dinic::build(u + v + 2);
  // int s = u + v, t = s + 1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      if (iu[i][j] != -1) {
        // cout << "U " << i << ' ' << j << '\n';
        // dinic::link(s, iu[i][j], 1);
        // link_(i, j, i - 1, j + 1);
        // link_(i, j, i + 1, j - 1);
      }
      if (iv[i][j] != -1) {
        // cout << "V " << i << ' ' << j << '\n';
        // dinic::link(u + iv[i][j], t, 1);
        link_(i + 1, j - 1, i, j);
        link_(i - 1, j + 1, i, j);
      }
      link_(i, j, i, j);
    }
  BipartiteGraph g(u, v, edge.size());
  for (auto [u, v] : edge)
    g.addEdge(u, v);
  // HopcroftKarp hk(u, v, edge);
  cout << u + v - g.maxMatchingEdges().size() << '\n';
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

dango_maker.cpp:12: warning: "assert" redefined
   12 | #define assert(...) 0
      | 
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from dango_maker.cpp:7:
/usr/include/assert.h:92: note: this is the location of the previous definition
   92 | #  define assert(expr)       \
      | 
dango_maker.cpp: In constructor 'BipartiteGraph::BipartiteGraph(int, int, int)':
dango_maker.cpp:20:16: warning: 'BipartiteGraph::Rpart' will be initialized after [-Wreorder]
   20 |     int Lpart, Rpart;
      |                ^~~~~
dango_maker.cpp:19:9: warning:   'int BipartiteGraph::n' [-Wreorder]
   19 |     int n;
      |         ^
dango_maker.cpp:29:5: warning:   when initialized here [-Wreorder]
   29 |     BipartiteGraph(int a, int b, int p = 0): Lpart(a), Rpart(b), n(a + b), matching_num(-1), num_starts(a + b + 1, 0), match(n, -1) {
      |     ^~~~~~~~~~~~~~
dango_maker.cpp: In constructor 'BipartiteGraph::BipartiteGraph(int, int, const std::vector<std::array<int, 2> >&)':
dango_maker.cpp:20:16: warning: 'BipartiteGraph::Rpart' will be initialized after [-Wreorder]
   20 |     int Lpart, Rpart;
      |                ^~~~~
dango_maker.cpp:19:9: warning:   'int BipartiteGraph::n' [-Wreorder]
   19 |     int n;
      |         ^
dango_maker.cpp:32:5: warning:   when initialized here [-Wreorder]
   32 |     BipartiteGraph(int a, int b, const vector<array<int, 2>>& Edges): Lpart(a), Rpart(b), n(a + b), matching_num(-1), raw_edges(Edges), num_starts(a + b + 1, 0), match(n, -1) {}
      |     ^~~~~~~~~~~~~~
dango_maker.cpp: In member function 'std::vector<std::array<int, 2> > BipartiteGraph::minimumEdgeCover()':
dango_maker.cpp:12:21: warning: statement has no effect [-Wunused-value]
   12 | #define assert(...) 0
      |                     ^
dango_maker.cpp:113:9: note: in expansion of macro 'assert'
  113 |         assert(n - matching_num == idx);
      |         ^~~~~~
dango_maker.cpp: In member function 'int BipartiteEdgeColoring::makeDRegular(int&, std::vector<std::pair<int, int> >&, int&)':
dango_maker.cpp:12:21: warning: statement has no effect [-Wunused-value]
   12 | #define assert(...) 0
      |                     ^
dango_maker.cpp:222:5: note: in expansion of macro 'assert'
  222 |     assert (cnt[0] >= cnt[1]);
      |     ^~~~~~
dango_maker.cpp:12:21: warning: statement has no effect [-Wunused-value]
   12 | #define assert(...) 0
      |                     ^
dango_maker.cpp:228:7: note: in expansion of macro 'assert'
  228 |       assert (e.first < e.second);
      |       ^~~~~~
dango_maker.cpp: In constructor 'BipartiteEdgeColoring::BipartiteEdgeColoring(int, int, std::vector<std::pair<int, int> >)':
dango_maker.cpp:12:21: warning: statement has no effect [-Wunused-value]
   12 | #define assert(...) 0
      |                     ^
dango_maker.cpp:314:7: note: in expansion of macro 'assert'
  314 |       assert(e.first < L && e.second < R);
      |       ^~~~~~
dango_maker.cpp:12:21: warning: statement has no effect [-Wunused-value]
   12 | #define assert(...) 0
      |                     ^
dango_maker.cpp:321:7: note: in expansion of macro 'assert'
  321 |       assert (e.first < L && e.second >= L);
      |       ^~~~~~
dango_maker.cpp:320:16: warning: unused variable 'e' [-Wunused-variable]
  320 |     for(auto &&e: edges){
      |                ^

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 0 / 67