Submission #853506

#	Time	Username	Problem	Language	Result	Execution time	Memory
853506		thinknoexit	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	18 ms	80616 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[3030][3030];
int b[3030][3030];
char c[3030][3030];
bool p[3000001], vis[3000001];
vector<int> adj[3000001];
const int di[4] = { 1,0,-1,0 }, dj[4] = { 0,1,0,-1 };
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> c[i][j];
            if (i >= 3) {
                if (c[i][j] == 'W' && c[i - 1][j] == 'G' && c[i - 2][j] == 'R') {
                    a[i][j] = a[i - 1][j] = a[i - 2][j] = ++cnt;
                    p[cnt] = 0;
                }
            }
            if (j >= 3) {
                if (c[i][j] == 'W' && c[i][j - 1] == 'G' && c[i][j - 2] == 'R') {
                    b[i][j] = b[i][j - 1] = b[i][j - 2] = ++cnt;
                    p[cnt] = 1;
                }
            }
        }
    }
    // // debug
    // for (int i = 1;i <= n;i++) {
    //     for (int j = 1;j <= m;j++) {
    //         cout << a[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    // for (int i = 1;i <= n;i++) {
    //     for (int j = 1;j <= m;j++) {
    //         cout << b[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    // // ----------
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (a[i][j] && b[i][j]) {
                adj[a[i][j]].push_back(b[i][j]);
                adj[b[i][j]].push_back(a[i][j]);
            }
        }
    }
    for (int i = 1;i <= cnt;i++) {
        if (vis[i]) continue;
        int c1 = 0, c2 = 0;
        queue<int> q;
        q.push(i);
        vis[i] = 1;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            if (p[v]) c1++;
            else c2++;
            for (auto& x : adj[v]) {
                if (vis[x]) continue;
                vis[x] = 1;
                q.push(x);
            }
        }
        ans += max(c1, c2);
    }
    cout << ans;
    return 0;
}

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