제출 #1289610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289610		dirtblock	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	1 ms	1148 KiB

dango_maker

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n,m; cin>>n>>m;
	vector<string> s(n);
	for(int i=0; i<n; i++) cin>>s[i];
	vector<int> idl(n*m,-1), idr(n*m,-1);
    int l=0,r=0;
    for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(s[i][j]=='G') {
				if(j>0&&j<m-1&&s[i][j-1]=='R'&&s[i][j+1]=='W') idl[i*m+j]=l++;
				if(i>0&&i<n-1&&s[i-1][j]=='R'&&s[i+1][j]=='W') idr[i*m+j]=r++;
			}
		}
    }
    vector<int> h(l,-1),to,nxt;
    auto addEdge=[&](int u,int v) {
		 nxt.push_back(h[u]);
		 to.push_back(v); 
		 h[u]=(int)to.size()-1; 
	};
    for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(s[i][j]=='G') continue;
			int lh=-1,rh=-1;
			if(s[i][j]=='R') {
				if(j<m-1) lh=idl[i*m+j+1];
				if(i<n-1) rh=idr[(i+1)*m+j];
			} 
			else {
				if(j>0) lh=idl[i*m+j-1];
				if(i>0) rh=idr[(i-1)*m+j];
			}
			if(lh!=-1&&rh!=-1) addEdge(lh,rh);
		}
    }
    vector<int> uu(l,-1),vv(r,-1),dist(l);
	function<bool()> bfs=[&]() {
        queue<int>q;
        for(int u=0; u<l; u++) {
            if(uu[u]==-1) {
				 dist[u]=0;
				 q.push(u); 
			}
            else dist[u]=-1;
        }
        bool r=false;
        while(!q.empty()) {
            int u=q.front(); 
            q.pop();
            for(int e=h[u]; e!=-1; e=nxt[e]) {
				int v=to[e];
                if(vv[v]==-1) r=true;
                else if(dist[vv[v]]==-1) {
                    dist[vv[v]]=dist[u]+1;
                    q.push(vv[v]);
                }
            }
        }
        return r;
    };
    function<bool(int)> dfs=[&](int u)->bool {
        for(int e=h[u]; e!=-1; e=nxt[e]) {
			int v=to[e];
            if(vv[v]==-1||(dist[vv[v]]==dist[u]+1&&dfs(vv[v]))) {
                uu[u]=v; vv[v]=u;
                return true;
            }
        }
        dist[u]=INT_MAX;
        return false;
    };
    int cnt=0;
    vector<int> temp=h;
    while(bfs()) {
		h=temp;
		for(int u=0; u<l; u++) {
			if(uu[u]==-1&&dfs(u)) cnt++;
		}
	}
	cout<<l+r-cnt;
	
	return 0;
}

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