Submission #164511

#	Time	Username	Problem	Language	Result	Execution time	Memory
164511		balbit	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	518 ms	262148 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define f first
#define s second
#define FOR(i,a,b) for (int i = a; i<b; i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for (int i = n-1; i>=0; i--)
#define SZ(x) (int)(x.size())
#define ALL(x) x.begin(),x.end()
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define pb push_back
#ifdef BALBIT
#define IOS()
#define bug(x) cerr<<__LINE__<<' '<<#x<<": "<<x<<endl
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(x)
#endif

const ll mod = 1e9+7;
const int maxn = 3e3+5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int iinf = 0x3f3f3f3f;


struct Edge{
	int to, rev; int cap; int flow = 0;
	Edge(int to, int rev, int cap) : to(to),rev(rev),cap(cap){
		
	}
};
int N , S, T;
vector<vector<Edge> > g;
vector<int> level;
vector<int> ptr; 

void add(int v, int u, int cap){
	g[v].pb({u,SZ(g[u]), cap});
	g[u].pb({v,SZ(g[v])-1, 0});
}

bool bfs(){
	fill(ALL(level), -1);
	level[S]=0;
	queue<int> q ({S});
	while (level[T]==-1 && !q.empty() ){
		int v = q.front(); q.pop();
		for (Edge &e : g[v]){
			if(e.cap-e.flow > 0 && level[e.to] == -1){
				level[e.to] = level[v]+1; 
				q.push(e.to);
			}
		}
	}
	return level[T]!=-1;
}

int dfs(int v, int amt){
	if(amt == 0 || v== T) return amt;
	for(; ptr[v] < SZ(g[v]); ptr[v]++){
		Edge &e = g[v][ptr[v]];
		if (level[e.to]!=level[v]+1) continue;
		int mo = dfs(e.to, min(amt,e.cap-e.flow));
		if (mo !=0 ) {
			e.flow += mo;
			g[e.to][e.rev].flow -= mo;
			return mo;
		}
	}
	return 0;
}

int mf(){
	int re = 0;
	while (bfs()){
		fill(ALL(ptr),0);
		while(int amt = dfs(S,iinf)) {
			re += amt;
		}
	}
	return re;
}
	


char grd[maxn][maxn];

int idup[maxn][maxn];
int idrt[maxn][maxn];


signed main(){
	IOS();
	int n, m; cin>>n>>m;
	
	REP(i,n) REP(j,m) cin>>grd[i][j];
	int nup = 0, nrt = 0;
	memset(idup, -1, sizeof(idup));
	memset(idrt, -1, sizeof(idrt));
	REP(i,n)REP(j,m){

		if(grd[i][j]=='G'){
			if (i && i!=n-1 && grd[i-1][j] == 'R' && grd[i+1][j]=='W' ) {
				idup[i][j] = nup++;
			}
			if (j && j!=m-1 && grd[i][j-1] == 'R' && grd[i][j+1]=='W' ) {
				idrt[i][j] = nrt ++;
			}
		}
	}

	N = nup + nrt + 5; S = N-1, T = N-2;
	g.resize(N); ptr.resize(N); level.resize(N);
	REP(i,n) REP(j,m){
		if(idup[i][j]!=-1){
//			cout<<i<<' '<<j<<' '<<idup[i][j]<<endl;
			add(S,idup[i][j],1);
			if(idrt[i][j] != -1) {
				add(idup[i][j], idrt[i][j] + nup, iinf);
			}
			if(i && idrt[i-1][j+1]!=-1){
				add(idup[i][j], idrt[i-1][j+1] + nup, iinf);
			}
			if(j && idrt[i+1][j-1]!=-1){
				add(idup[i][j], idrt[i+1][j-1] + nup, iinf);
			}
		}
		if(idrt[i][j]!=-1){
			add(idrt[i][j] + nup, T, 1);
		}
	}
	cout<<nup + nrt - mf() << endl;
	
}

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