제출 #164498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
164498		balbit	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	563 ms	262144 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 Dinic{
	struct Edge{
		int to, rev; ll cap; ll flow = 0;
		Edge(int to, int rev, ll cap) : to(to),rev(rev),cap(cap){
			
		}
	};
	int n , S, T;
	vector<vector<Edge> > g;
	vector<int> level;
	vector<int> ptr; 
	Dinic(int n, int S, int T) : n(n), S(S), T(T){
		g.resize(n); level.resize(n); ptr.resize(n);
	}
	void add(int v, int u, ll 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;
	}
	
	ll dfs(int v, ll 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;
			ll 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;
	}
	
	ll mf(){
		ll re = 0;
		while (bfs()){
			fill(ALL(ptr),0);
			while(ll amt = dfs(S,INF)) {
				re += amt;
			}
		}
		return re;
	}
	
};

char grd[maxn][maxn];
bool up[maxn][maxn]; // Can this g go up?
bool rt[maxn][maxn]; // Can this g go right?
int idup[maxn][maxn];
int idrt[maxn][maxn];


int id(int r, int c){
	
}

signed main(){
	IOS();
	int n, m; cin>>n>>m;
	REP(i,n) REP(j,m) cin>>grd[i][j];
	int nup = 0, nrt = 0;
	REP(i,n)REP(j,m){
		if(grd[i][j]=='G'){
			up[i][j] = (i && i!=n-1 && grd[i-1][j] == 'R' && grd[i+1][j]=='W' );
			rt[i][j] = (j && j!=m-1 && grd[i][j-1] == 'R' && grd[i][j+1]=='W' );
			idup[i][j] = nup; idrt[i][j] = nrt;
			nup += up[i][j]; 
			nrt += rt[i][j]; 
		}
	}
	int N = nup + nrt + 5; int S = N-1, T = N-2;
	Dinic dd (N,S,T);
	REP(i,n) REP(j,m){
		if(up[i][j]){
//			cout<<i<<' '<<j<<' '<<idup[i][j]<<endl;
			dd.add(S,idup[i][j],1);
			if(rt[i][j] ) {
				dd.add(idup[i][j], idrt[i][j] + nup, iinf);
			}
			if(i && rt[i-1][j+1]){
				dd.add(idup[i][j], idrt[i-1][j+1] + nup, iinf);
			}
			if(j && rt[i+1][j-1]){
				dd.add(idup[i][j], idrt[i+1][j-1] + nup, iinf);
			}
		}
		if(rt[i][j]){
//			cout<<"rt: "<<i<<' '<<j<<' '<<idrt[i][j]<<endl;
			dd.add(idrt[i][j] + nup, T, 1);
		}
	}
//	bug(nup + nrt);
	cout<<nup + nrt - dd.mf() << endl;
	
}

컴파일 시 표준 에러 (stderr) 메시지

dango_maker.cpp: In function 'int id(int, int)':
dango_maker.cpp:101:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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