oj.uz

Submission #164501

# Submission time Handle Problem Language Result Execution time Memory
164501 2019-11-21T07:25:34 Z balbit Dango Maker (JOI18_dango_maker) C++14
13 / 100
 4 ms 380 KB 
#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; 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; 
	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, 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;
	REP(i,n)REP(j,m){
		idup[i][j] = idrt[i][j] = -1;
		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 ++;
			}
		}
	}

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

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 296 KB Output is correct
15 Correct 4 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 296 KB Output is correct
15 Correct 4 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Incorrect 2 ms 380 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 296 KB Output is correct
15 Correct 4 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Incorrect 2 ms 380 KB Output isn't correct
19 Halted 0 ms 0 KB -