Submission #924634

#	Time	Username	Problem	Language	Result	Execution time	Memory
924634		thinknoexit	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	26 ms	82776 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3000001;
int a[3030][3030];
int b[3030][3030];
char c[3030][3030];
int deg[N];
bool p[N], vis[N];
vector<int> adj[N];
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') {
                    cnt++;
                    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') {
                    cnt++;
                    b[i][j] = b[i][j - 1] = b[i][j - 2] = cnt;
                    p[cnt] = 1;
                }
            }
        }
    }
    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]);
                deg[a[i][j]]++;
                deg[b[i][j]]++;
            }
        }
    }
    for (int i = 1;i <= cnt;i++) {
        if (vis[i]) continue;
        int c1 = 0, c2 = 0;
        int d1 = 0, d2 = 0;
        queue<int> q;
        q.push(i);
        vis[i] = 1;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            if (p[v]) {
                c1++;
                if (deg[v] == 1) d1++;
            }
            else {
                c2++;
                if (deg[v] == 1) d2++;
            }
            for (auto& x : adj[v]) {
                if (vis[x]) continue;
                vis[x] = 1;
                q.push(x);
            }
        }
        int res = max(c1, c2);
        if (d1 >= 2) res = max(res, c2 + 1);
        if (d2 >= 2) res = max(res, c1 + 1);
        ans += res;
    }
    cout << ans;
    return 0;
}

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