제출 #1133322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133322		Pekiban	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	55 ms	71608 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;
#define pb push_back

const int N = 3e6 + 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);
    ex.reset(); vis.reset();
    for (int i = 1; i < N; ++i) g[i].clear();
    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');
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (ex[H(i, j, 0)]) {
                for (int t = 0; t <= 2; ++t) {
                    if (i <= n-t && ex[H(i+t, j-t, 1)]) g[H(i, j, 0)].pb(H(i+t, j-t, 1));
                }
            }
            if (ex[H(i, j, 1)]) {
                for (int t = 0; t <= 2; ++t) {
                    if (j <= n-t && ex[H(i-t, j+t, 0)]) g[H(i, j, 1)].pb(H(i-t, j+t, 0));
                }
            }
        }
    }
    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: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67