Submission #1133308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133308		Pekiban	Dango Maker (JOI18_dango_maker)	C++20	0 / 100	141 ms	327680 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;
#define pb push_back

const int N = 2e7 + 10; // cooked
vector<int> g[N];
bitset<N> ex, vis;
int n, m;
int H(int x, int y, bool b) {
    return (m + 1) * x + y + b * (N / 2);
}
int sz = 0;
void dfs(int s) {
    vis[s] = 1, sz++;
    for (auto u : g[s]) {
        if (vis[u]) continue;
        dfs(u);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    char a[n+1][m+1];
    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) {
            ex[H(i, j, 0)] = (j >= 3 && a[i][j] == 'W' && a[i][j-1] == 'G' && a[i][j-2] == 'R');
            ex[H(i, j, 1)] = (i >= 3 && a[i][j] == 'W' && a[i-1][j] == 'G' && a[i-2][j] == 'R');
        }
    }
    auto add = [&](int x, int y) {
        g[x].pb(y); g[y].pb(x);
    };
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (ex[H(i, j, 0)]) {
                if (ex[H(i, j, 1)]) add(H(i, j, 0), H(i, j, 1));
                if (i <= n-1 && ex[H(i+1, j-1, 1)]) add(H(i, j, 0), H(i+1, j-1, 1));
                if (i <= n-2 && ex[H(i+2, j-2, 1)]) add(H(i, j, 0), H(i+2, j-2, 1));
            }
        }
    }
    int ans = 0;
    for (int i = 1; i < N; ++i) {
        if (ex[i] && !vis[i]) {
            sz = 0;
            dfs(i);
            ans += (sz+1)/2;
        }
    }
    cout << ans << '\n';
}

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