This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #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;
}
Compilation message (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){
| ^| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
