#include<bits/stdc++.h>
using namespace std;
// Edge structure: handles node pointed to, capacity
// and the index in v[to] to its reverse edge
struct Edge{
int to, rev;
int cap; //
bool is_rev;
Edge(int t, int c, int r, bool irev):to{t},rev{r},cap{c},is_rev{irev}
{}
};
struct Flow{
int n, s, t; // n: # nodes, s: source, t: sink
vector<vector<Edge>> v; // extended adj list
vector<int> lvl; // indicates the lvl for each node. used for the lvl graph
// assures that each edge is completely visited only once. keeps sort of backup
// of the index of the last visited edge
// there is no need to revisit an edge, hence, these can be skipped
vector<int> lastPos;
// constructor
Flow(int N, int src, int snk){
this->n = N;
this->s = src;
this->t = snk;
v = vector<vector<Edge>>(n, vector<Edge>());
}
// adding edges: endpoints and capacities
// in case of bidirecitonal edges, use this function twice, one for each direction
// using the full capacity on both
void addEdge(int a, int b, int c){
v[a].push_back({b,c,(int)v[b].size(),false});
v[b].push_back({a,0,((int)v[a].size()) - 1,true});
}
// "builds" the lvl graph. simple bfs indicating the lvl for each node
void getLvls(){
queue<int> q; q.push(s);
lvl.assign(n,-1); lvl[s] = 0;
while(q.size()){
int x = q.front(); q.pop();
for(auto e : v[x]){
if(lvl[e.to] == -1 && e.cap){
// lvl graph only reaches new nodes and possible edges (cap > 0)
q.push(e.to);
lvl[e.to] = lvl[x] + 1;
}
}
}
}
// finds an augmenting path and updates edges
int dfs(int i, int curr = INT_MAX){
if(i == t){
return curr; // reached sink, returning collected flow
}else{
for(; lastPos[i] < v[i].size(); ++lastPos[i]){
auto &e = v[i][lastPos[i]];
if(e.cap && lvl[i] + 1 == lvl[e.to]){
// possible edges (cap > 0) and lvl-graph structure (consecutive lvls traversal)
int maybe_flow = dfs(e.to, min(curr, e.cap));
if(maybe_flow == 0) continue;
e.cap -= maybe_flow; // updating edge
v[e.to][e.rev].cap += maybe_flow; // and its reverse
return maybe_flow;
}
}
}
return 0;
}
// main funct
int run(){
int flow = 0; // initial flow
while(true){
getLvls(); // builds lvl graph
// if the sink cant be reached, the max flow has been found
if(lvl[t]==-1) break;
// get a blocking flow for the current lvl graph
int blocking = -1;
lastPos.assign(n,0);
while((blocking = dfs(s))) flow += blocking;
}
return flow;
}
vector<pair<int,int>> get_cut(){
vector<pair<int,int>> cut;
for(int i = 0; i < n; ++i){
for(int j = 0; j < v[i].size(); ++j){
auto &e = v[i][j];
if(!e.is_rev && lvl[i] != -1 && lvl[e.to] == -1){
cut.push_back({i, e.to});
}
}
}
return cut;
}
};
const int SRC = 0;
const int SINK = 1;
const int OFFSET = 2;
const int MAXN = 3001;
string s[MAXN];
int idv[MAXN][MAXN];
int idh[MAXN][MAXN];
int main(){
memset(idv, -1, sizeof idv);
memset(idh, -1, sizeof idh);
cin.tie(NULL)->sync_with_stdio(false);
int n, m; cin >> n >> m;
for(int i = 0; i < n; ++i){
cin >> s[i];
}
int curr_idv = 0;
int curr_idh = 0;
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
// ver
if(i + 2 < n){
if((s[i][j] == 'R') && (s[i+1][j] == 'G') && (s[i+2][j] == 'W')){
idv[i][j] = curr_idh;
idv[i+1][j] = curr_idh;
idv[i+2][j] = curr_idh;
curr_idh++;
}
}
if(j + 2 < m){
if((s[i][j] == 'R') && (s[i][j+1] == 'G') && (s[i][j+2] == 'W')){
idh[i][j] = curr_idv;
idh[i][j+1] = curr_idv;
idh[i][j+2] = curr_idv;
curr_idv++;
}
}
}
}
for(int i = 0; i < n; ++i) s[i].clear();
Flow f(2 + curr_idh + curr_idv, SRC, SINK);
for(int i = 0; i < curr_idv; ++i){
f.addEdge(SRC, i + OFFSET, 1);
}
for(int i = 0; i < curr_idh; ++i){
f.addEdge(i + curr_idv + OFFSET, SINK, 1);
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
if(idh[i][j] != -1 && idv[i][j] != -1){
// cout << i << " " << j << " " << idv[i][j][0] << " " << idh[i][j][0] << endl;
f.addEdge(idv[i][j] + OFFSET, curr_idv + idh[i][j] + OFFSET, 1);
}
}
}
int x = f.run();
// cout << x << " " << curr_idh << " " << curr_idv<< endl;
cout << curr_idh + curr_idv - x << "\n";
}
Compilation message
dango_maker.cpp: In member function 'int Flow::dfs(int, int)':
dango_maker.cpp:62:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(; lastPos[i] < v[i].size(); ++lastPos[i]){
dango_maker.cpp: In member function 'std::vector<std::pair<int, int> > Flow::get_cut()':
dango_maker.cpp:97:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int j = 0; j < v[i].size(); ++j){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
70868 KB |
Output is correct |
| 2 |
Correct |
29 ms |
70860 KB |
Output is correct |
| 3 |
Correct |
31 ms |
70824 KB |
Output is correct |
| 4 |
Correct |
29 ms |
70864 KB |
Output is correct |
| 5 |
Correct |
27 ms |
70860 KB |
Output is correct |
| 6 |
Correct |
28 ms |
70916 KB |
Output is correct |
| 7 |
Incorrect |
28 ms |
70884 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
70868 KB |
Output is correct |
| 2 |
Correct |
29 ms |
70860 KB |
Output is correct |
| 3 |
Correct |
31 ms |
70824 KB |
Output is correct |
| 4 |
Correct |
29 ms |
70864 KB |
Output is correct |
| 5 |
Correct |
27 ms |
70860 KB |
Output is correct |
| 6 |
Correct |
28 ms |
70916 KB |
Output is correct |
| 7 |
Incorrect |
28 ms |
70884 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
70868 KB |
Output is correct |
| 2 |
Correct |
29 ms |
70860 KB |
Output is correct |
| 3 |
Correct |
31 ms |
70824 KB |
Output is correct |
| 4 |
Correct |
29 ms |
70864 KB |
Output is correct |
| 5 |
Correct |
27 ms |
70860 KB |
Output is correct |
| 6 |
Correct |
28 ms |
70916 KB |
Output is correct |
| 7 |
Incorrect |
28 ms |
70884 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
