Submission #704527

#	Time	Username	Problem	Language	Result	Execution time	Memory
704527		KenIsGenius	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	246 ms	262144 KiB

dango_maker

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define ll long long
using namespace std;

#ifdef LOCAL
#define WOSAOJI freopen("in.txt", "r", stdin);
#else
#define WOSAOJI ios_base::sync_with_stdio(0), cin.tie(0);
#endif

#define chmax(a, b) (a) = (a) > (b) ? (a) : (b)
#define chmin(a, b) (a) = (a) < (b) ? (a) : (b)

int n, m, cnt;
char c[3005][3005];
int a[3005][3005];
vector<int> adj[9000005];

void add_edge(int a, int b) {
    adj[a].pb(b);
    adj[b].pb(a);
}
bool crow(int i, int j) {
    int ok = 1;
    ok &= (c[i][j - 2] == 'R');
    ok &= (c[i][j - 1] == 'G');
    ok &= (c[i][j    ] == 'W');
    return ok;
}
bool col(int i, int j) {
    int ok = 1;
    ok &= (c[i - 2][j] == 'R');
    ok &= (c[i - 1][j] == 'G');
    ok &= (c[i    ][j] == 'W');
    return ok;
}
int match[9000005];
void dfs(int x, int v) {
    match[x] = v;
    for (int i : adj[x]) {
        if (match[i] == v) {
            dfs(i, v ^ 1);
            return;
        }
    }
}
signed main() {
    WOSAOJI
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
            if (j >= 3 and crow(i, j)) {
                cnt++;
                a[i][j] = a[i][j - 1] = a[i][j - 2] = cnt;
            }
        }
    }
    for (int i = 3; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (col(i, j)) {
                cnt++;
                if (a[i - 2][j])
                    add_edge(a[i - 2][j], cnt);
                if (a[i - 1][j])
                    add_edge(a[i - 1][j], cnt);
                if (a[i    ][j])
                    add_edge(a[i    ][j], cnt);
            }
        }
    }
    for (int i = 1; i <= cnt; i++) {
        if (!match[i]) dfs(i, 1);
    }
    int ans = 0;
    for (int i = 1; i <= cnt; i++) {
        ans += match[i];
    }
    cout << ans << '\n';
}

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