Submission #164517

#	Time	Username	Problem	Language	Result	Execution time	Memory
164517		balbit	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	470 ms	239224 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;


#define MAX 300001
#define NIL 0
#define INF (1<<28)

vector< int > G[MAX];
int N, M, match[MAX], dist[MAX];
// n: number of nodes on left side, nodes are numbered 1 to n
// m: number of nodes on right side, nodes are numbered n+1 to n+m
// G = NIL[0] ∪ G1[G[1---n]] ∪ G2[G[n+1---n+m]]

bool bfs() {
    int i, u, v, len;
    queue< int > Q;
    for(i=1; i<=N; i++) {
        if(match[i]==NIL) {
            dist[i] = 0;
            Q.push(i);
        }
        else dist[i] = INF;
    }
    dist[NIL] = INF;
    while(!Q.empty()) {
        u = Q.front(); Q.pop();
        if(u!=NIL) {
            len = G[u].size();
            for(i=0; i<len; i++) {
                v = G[u][i];
                if(dist[match[v]]==INF) {
                    dist[match[v]] = dist[u] + 1;
                    Q.push(match[v]);
                }
            }
        }
    }
    return (dist[NIL]!=INF);
}

bool dfs(int u) {
    int i, v, len;
    if(u!=NIL) {
        len = G[u].size();
        for(i=0; i<len; i++) {
            v = G[u][i];
            if(dist[match[v]]==dist[u]+1) {
                if(dfs(match[v])) {
                    match[v] = u;
                    match[u] = v;
                    return true;
                }
            }
        }
        dist[u] = INF;
        return false;
    }
    return true;
}

int hopcroft_karp() {
    int matching = 0, i;
    // match[] is assumed NIL for all vertex in G
    while(bfs())
        for(i=1; i<=N; i++)
            if(match[i]==NIL && dfs(i))
                matching++;
    return matching;
}
	


char grd[maxn][maxn];

int idup[maxn][maxn];
int idrt[maxn][maxn];
bool up[maxn][maxn];
bool rt[maxn][maxn];


void add(int a, int b, int c){
//	return;
	G[a].pb(b);
}

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'){
			if (i && i!=n-1 && grd[i-1][j] == 'R' && grd[i+1][j]=='W' ) {
				up[i][j] = 1;
			}
			if (j && j!=m-1 && grd[i][j-1] == 'R' && grd[i][j+1]=='W' ) {
				rt[i][j] = 1;
			}
		}
	}


//	g.resize(N); ptr.resize(N); level.resize(N);
	int ans = 0;
	REP(i,n) REP(j,m){
		if(up[i][j]){
//			cout<<i<<' '<<j<<' '<<idup[i][j]<<endl;
			bool B = 0;
			if(rt[i][j]) B=1, idrt[i][j] = 1;
			if(i && rt[i-1][j+1]) B=1, idrt[i-1][j+1] = 1;
			if(j && rt[i+1][j-1]) B=1, idrt[i+1][j-1] = 1;
			nup += B; 	
			idup[i][j] = B;
			if (!B) ans ++;
		}
	}
	int nat = 0;
	REP(i,n) REP(j,m){
		if (idrt[i][j]){
			idrt[i][j] = ++nat; 
		}else if (rt[i][j]) ans ++;
	}
	nrt = nat; 
	nat = 0;
	REP(i,n) REP(j,m){
		if(idup[i][j]){
			idup[i][j] = ++nat;
//			cout<<i<<' '<<j<<' '<<idup[i][j]<<endl;
			if(idrt[i][j]) {
				add(idup[i][j], idrt[i][j] + nup, iinf);
			}
			if(i && idrt[i-1][j+1]){
				add(idup[i][j], idrt[i-1][j+1] + nup, iinf);
			}
			if(j && idrt[i+1][j-1]){
				add(idup[i][j], idrt[i+1][j-1] + nup, iinf);
			}
		}

	}
	bug(ans);
	N = nup; 
	bug(nup); bug(nrt); 
	cout<<ans + nup + nrt - hopcroft_karp() << endl;
	
}

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