#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
//#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pdd pair<double ,double>
#define pcc pair<char, char>
#define endl '\n'
// #define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif
const ll inf = (1ll<<60);
const int iinf=2147483647;
const ll mod = 1e9+7;
const ll maxn=3005;
//const ll sqmaxn=9000005;
const double PI=acos(-1);
ll pw(ll x, ll p, ll m=mod){
ll ret=1;
while (p>0){
if (p&1){
ret*=x;
ret%=m;
}
x*=x;
x%=m;
p>>=1;
}
return ret;
}
ll inv(ll a, ll m=mod){
return pw(a,m-2);
}
struct Dinic{
static const int sqmaxn=18000010;
int n, s, t;
int cur[sqmaxn], lev[sqmaxn];
struct Edge{
int to, cap, rev;
//Edge(){}
//Edge(int _to, int _cap, int _rev): to(_to), cap(_cap), rev(_rev){}
};
vector<Edge> G[sqmaxn];
void insert(int _from, int _to, int _cap){
G[_from].pb({_to, _cap, SZ(G[_to])});
G[_to].pb({_from, 0, SZ(G[_from])-1});
}
void bfs(){
queue<int> qu;
qu.push(s);
fill(lev, lev+sqmaxn, -1);
lev[s]=0;
while(qu.size()){
int x=qu.front(); qu.pop();
//cout<<x<<endl;
//cout<<G[x].size()<<endl;
REP(i,SZ(G[x])){
if (lev[G[x][i].to]==-1&&G[x][i].cap>0){
lev[G[x][i].to]=lev[x]+1;
qu.push(G[x][i].to);
}
}
}
}
int dfs(int x, int infl){
if (infl==0||x==t) return infl;
int fl=0;
for (int &i=cur[x]; i<SZ(G[x]); i++){
Edge e=G[x][i];
if (lev[e.to]!=lev[x]+1||e.cap<=0){
continue;
}
int ret=dfs(e.to, min(e.cap, infl));
if (ret>0){
fl+=ret;
infl-=ret;
G[x][i].cap-=ret;
G[e.to][e.rev].cap+=ret;
if (infl==0) break;
}
}
return fl;
}
int maxflow(int _s, int _t){
s=_s; t=_t;
int res=0;
while(1){
bfs();
//cout<<lev[t]<<endl;
if (lev[t]==-1) break;
int curres;
fill(cur, cur+sqmaxn, 0);
while((curres=dfs(s, iinf))>0){
res+=curres;
}
}
return res;
}
}ok;
char arr[maxn][maxn];
int val[maxn][maxn];
signed main(){
IOS();
int n,m; cin>>n>>m;
REP1(i,n){
REP1(j,m) {
cin>>arr[i][j];
}
}
int cval=3;
REP1(i,n){
REP1(j,m){
if (arr[i][j-1]=='R'&&arr[i][j]=='G'&&arr[i][j+1]=='W'){
val[i][j]=cval;
ok.insert(1, cval, 1);
bug(cval);
cval++;
}
}
}
REP1(i,n){
REP1(j,m){
if (arr[i-1][j]!='R'||arr[i][j]!='G'||arr[i+1][j]!='W'){
continue;
}
ok.insert(cval, 2, 1);
if (val[i-1][j+1]!=0){
ok.insert(val[i-1][j+1], cval, 1);
bug(cval);
}
if (val[i+1][j-1]!=0){
ok.insert(val[i+1][j-1], cval, 1);
bug(cval);
}
bug(cval);
cval++;
}
}
int okans=ok.maxflow(1, 2);
cout<<cval-okans-3<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
