| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 853378 | willychan | Dango Maker (JOI18_dango_maker) | C++14 | 0 ms | 0 KiB |
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<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
#define vi vector<int>
#define sz size
struct PushRelabel {
struct Edge {
int dest, back;
ll f, c;
};
vector<vector<Edge>> g;
vector<ll> ec;
vector<Edge*> cur;
vector<vi> hs; vi H;
PushRelabel(int n) : g(n), ec(n), cur(n), hs(2*n), H(n) {}
void add_edge(int s, int t, ll cap, ll rcap=0) {
if (s == t) return;
g[s].push_back({t, sz(g[t]), 0, cap});
g[t].push_back({s, sz(g[s])-1, 0, rcap});
}
void addFlow(Edge& e, ll f) {
Edge &back = g[e.dest][e.back];
if (!ec[e.dest] && f) hs[H[e.dest]].push_back(e.dest);
e.f += f; e.c -= f; ec[e.dest] += f;
back.f -= f; back.c += f; ec[back.dest] -= f;
}
ll calc(int s, int t) {
int v = sz(g); H[s] = v; ec[t] = 1;
vi co(2*v); co[0] = v-1;
for(int i=0;i<v;i++) cur[i] = g[i].data();
for (Edge& e : g[s]) addFlow(e, e.c);
for (int hi = 0;;) {
while (hs[hi].empty()) if (!hi--) return -ec[s];
int u = hs[hi].back(); hs[hi].pop_back();
while (ec[u] > 0) // discharge u
if (cur[u] == g[u].data() + sz(g[u])) {
H[u] = 1e9;
for (Edge& e : g[u]) if (e.c && H[u] > H[e.dest]+1)
H[u] = H[e.dest]+1, cur[u] = &e;
if (++co[H[u]], !--co[hi] && hi < v)
for(int i=0;i<v;i++) if (hi < H[i] && H[i] < v)
--co[H[i]], H[i] = v + 1;
hi = H[u];
} else if (cur[u]->c && H[u] == H[cur[u]->dest]+1)
addFlow(*cur[u], min(ec[u], cur[u]->c));
else ++cur[u];
}
}
bool leftOfMinCut(int a) { return H[a] >= sz(g); }
} ;
/*struct DINIC{
struct edge{
int to;
ll cap;
int rev;
};
vector<vector<edge> > side;
vector<int> level;
vector<int> next;
int n;
void init(int s){
n = s;
side.resize(n);
level.resize(n,0);
next.resize(n,0);
for(int i=0;i<n;i++) side[i].clear();
}
void add_edge(int a,int b,ll c){
// cout<<a<<"->"<<b<<"\n";
side[a].push_back({b,c,(int)(side[b].size())});
side[b].push_back({a,0,(int)(side[a].size()-1)});
}
bool bfs(int s,int t){
fill(level.begin(),level.end(),-1);
queue<int> q;
level[s]=0;
q.push(s);
while(q.size()){
int cur = q.front();
q.pop();
for(auto e : side[cur]){
if(e.cap<=0) continue;
if(level[e.to]<0){
level[e.to] = level[cur]+1;
q.push(e.to);
}
}
}
return (level[t]!=-1);
}
ll dfs(int v,int t,ll flow){
if(v==t) return flow;
for(;next[v]<side[v].size();next[v]++){
auto& e = side[v][next[v]];
if(e.cap<=0 || level[v]+1!=level[e.to]) continue;
ll ans = dfs(e.to,t,min(flow,e.cap));
if(ans>0){
e.cap-=ans;
side[e.to][e.rev].cap+=ans;
return ans;
}
}
return 0;
}
ll flow(int s,int t){
ll ans= 0;
while(bfs(s,t)){
fill(next.begin(),next.end(),0);
ll f = 0;
while((f=dfs(s,t,1e18))>0){
ans+=f;
}
}
return ans;
}
} graph;*/
int main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m;cin>>n>>m;
vector<vector<char>> grid(n,vector<char>(m));
vector<vector<int> > taken(n,vector<int>(m,0));
for(int i=0;i<n;i++){
string s;cin>>s;
for(int j=0;j<m;j++){
grid[i][j] = s[j];
}
}
int cnt = 0;
for(int i=0;i<n;i++){
for(int j=0;j+2<m;j++){
if(grid[i][j]=='R' && grid[i][j+1]=='G' && grid[i][j+2]=='W'){
cnt++;
taken[i][j]=cnt;
taken[i][j+1]=cnt;
taken[i][j+2]=cnt;
}
}
}
//cout<<cnt<<" ";
int total = cnt;
for(int j=0;j<m;j++){
for(int i=0;i+2<n;i++){
total+=(grid[i][j]=='R' && grid[i+1][j]=='G' && grid[i+2][j]=='W');
}
}
//cout<<total<<"\n";
PushRelabel graph(total+2) ;
int ton = cnt;
for(int j=0;j<m;j++){
for(int i=0;i+2<n;i++){
if(grid[i][j]=='R' && grid[i+1][j]=='G' && grid[i+2][j]=='W'){
ton++;
if(taken[i][j]) graph.add_edge(taken[i][j],ton,1);
if(taken[i+1][j]) graph.add_edge(taken[i+1][j],ton,1);
if(taken[i+2][j]) graph.add_edge(taken[i+2][j],ton,1);
}
}
}
for(int i=1;i<=cnt;i++){
graph.add_edge(0,i,1);
}
for(int i=cnt+1;i<=total;i++){
graph.add_edge(i,total+1,1);
}
ll ans = graph.calc(0,total+1);
cout<<total-ans<<"\n";
return 0;
}