Submission #477466

#	Time	Username	Problem	Language	Result	Execution time	Memory
477466		FireGhost1301	Dango Maker (JOI18_dango_maker)	C++11	33 / 100	274 ms	113864 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

const int N = 3e3 + 1;
int n, m, id[N][N][2], cnt;
char c[N][N];
vector<vector<int>> g;
vector<int> deg;
vector<bool> vst;

inline bool check(char x, char y, char z) {
    return (x == 'R' && y == 'G' && z == 'W');
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)
            cin >> c[i][j];
    }
    for (int i = 1; i + 2 <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (check(c[i][j], c[i + 1][j], c[i + 2][j]))
                id[i][j][0] = ++cnt;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j + 2 <= m; ++j) {
            if (check(c[i][j], c[i][j + 1], c[i][j + 2]))
                id[i][j][1] = ++cnt;
        }
    }
    g.resize(cnt + 1);
    deg.resize(cnt + 1, 0);
    vst.resize(cnt + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (!id[i][j][1]) continue;
            if (id[i][j][0]) {
                g[id[i][j][0]].pb(id[i][j][1]);
                g[id[i][j][1]].pb(id[i][j][0]);
                ++deg[id[i][j][0]], ++deg[id[i][j][1]];
            }
            if (i - 1 > 0) {
                if (id[i - 1][j + 1][0]) {
                    g[id[i - 1][j + 1][0]].pb(id[i][j][1]);
                    g[id[i][j][1]].pb(id[i - 1][j + 1][0]);
                    ++deg[id[i - 1][j + 1][0]], ++deg[id[i][j][1]];
                }
            }
            if (i - 2 > 0) {
                if (id[i - 2][j + 2][0]) {
                    g[id[i - 2][j + 2][0]].pb(id[i][j][1]);
                    g[id[i][j][1]].pb(id[i - 2][j + 2][0]);
                    ++deg[id[i - 2][j + 2][0]], ++deg[id[i][j][1]];
                }
            }
        }
    }
    int ans = 0;
    set<pii> st;
    for (int i = 1; i <= cnt; ++i) {
        if (!deg[i]) {
            ++ans;
            continue;
        }
        st.insert(mp(deg[i], i));
    }
    if (n * m >= 4000000) {
        cout << ans;
        return;
    }
    while (!st.empty()) {
        ++ans;
        auto it = st.begin();
        pii x = *it;
        int u = x.se;
        st.erase(it);
        vst[u] = true;
        for (int v: g[u]) {
            if (vst[v]) continue;
            st.erase(st.find(mp(deg[v], v)));
            vst[v] = true;
            for (int q: g[v]) {
                if (!vst[q]) {
                    st.erase(st.find(mp(deg[q], q)));
                    --deg[q];
                    st.insert(mp(deg[q], q));
                }
            }
        }
    }
    cout << ans;
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

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