Submission #1306302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306302		duyanhchupapi	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	409 ms	206500 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std; 
using ll = long long; 
const int N = 3e3 + 3, M = 3e6 + 3;
int n, m, _n, _m, id[N][N], iter = 0;
basic_string <int> g[M];
char a[N][N];
bool col[N][N];
bool stick(char A, char B, char C) {
	if (A == 'R' && B == 'G' && C == 'W') return true;
	return false;
}

vector <int> seen, dist, matchL, matchR;

bool dfs(int u) {
    if(seen[u] == iter) return 0;
    seen[u] = iter;

    for(int v : g[u]) {
        if(matchR[v] == -1) {
            matchL[u] = v; 
			matchR[v] = u;
            return 1;
        }
    }

    for(int v : g[u]) {
        if(dist[matchR[v]] == dist[u] + 1 && dfs(matchR[v])) {
            matchL[u] = v; 
			matchR[v] = u;
            return 1;
        }
    }

    return 0;
}

int main() { 
	ios_base::sync_with_stdio(0); cin.tie(0);
	// freopen(".INP", "r", stdin);
	// freopen(".OUT", "w", stdout);
	cin >> _n >> _m;

	for (int i=1;i<=_n;++i) 
		for (int j=1;j<=_m;++j) cin >> a[i][j];
		
	for (int i=1;i<=_n;++i) {
		for (int j=1;j<=_m;++j) {
			if (stick(a[i][j], a[i + 1][j], a[i + 2][j])) {
				col[i][j] = 1;
				id[i][j] = ++n;
			}
			
			if (stick(a[i][j], a[i][j + 1], a[i][j + 2])) {
				m++;
				if (col[i][j]) g[id[i][j]].push_back(m);
				if (col[i - 1][j + 1]) g[id[i - 1][j + 1]].push_back(m);
				if (i != 1 && col[i - 2][j + 2]) g[id[i - 2][j + 2]].push_back(m);
 			}

		}
	} 
	
	matchL.assign(n + 1, -1);
	matchR.assign(m + 1, -1);
	dist.assign(n + 1, 0);
	seen.assign(n + 1, 0);
	
    int ans = 0;
    while (1) {
        queue <int> q;
        for(int u = 1; u <= n; ++u) {
            if(matchL[u] == -1) dist[u] = 0, q.push(u);
            else dist[u] = -1;
        }

        while(q.size()) {
            int u = q.front(); 
			q.pop();
			
            for(int v : g[u]) {
                if(matchR[v] != -1 && dist[matchR[v]] == -1) {
                    dist[matchR[v]] = dist[u] + 1;
                    q.push(matchR[v]);
                }
            }
        }

        int add = 0;
        ++iter;
        for(int u = 1; u <= n; ++u) 
			if(matchL[u] == -1) add += dfs(u);
        
        if(add == 0) break;
        ans += add;
    }
	
	cout << n + m - ans;
} 

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