Submission #1125250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125250		eysbutno	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	1 ms	328 KiB

dango_maker

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

using ll = long long;
using pii = array<int, 2>;

#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for (string &i : grid) {
        cin >> i;
    }
    vector vert(n, vector<int>(m, -1));
    vector horiz(n, vector<int>(m, -1));
    int timer = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j + 2 < m; j++) {
            string res = "";
            for (int k = 0; k < 3; k++) {
                res += grid[i][j + k];
            }
            if (res != "RGW") continue;
            int id = timer++;
            for (int k = 0; k < 3; k++) {
                horiz[i][j + k] = id;
            }
        }
    }
    for (int i = 0; i + 2 < n; i++) {
        for (int j = 0; j < m; j++) {
            string res = "";
            for (int k = 0; k < 3; k++) {
                res += grid[i + k][j];
            }
            if (res != "RGW") continue;
            int id = timer++;
            for (int k = 0; k < 3; k++) {
                vert[i + k][j] = id;
            }
        }
    }
    vector<vector<int>> adj(timer);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int a = vert[i][j], b = horiz[i][j];
            if (a != -1 && b != -1) {
                adj[a].push_back(b);
                adj[b].push_back(a);
            }
        }
    }
    vector<int> col(timer, -1);
    const auto most_dangos = [&](int src) -> int {
        int nodes = 0, sum = 0;
        const auto dfs = [&](int u, auto &&self) -> void {
            nodes++;
            sum += col[u];
            for (int v : adj[u]) {
                if (col[v] != -1) {
                    assert(!col[u] == col[v]);
                } else {
                    col[v] = !col[u];
                    self(v, self);
                }
            }
        };
        col[src] = 0;
        dfs(src, dfs);
        return max(sum, nodes - sum);
    };
    int res = 0;
    for (int i = 0; i < timer; i++) {
        if (col[i] >= 0) continue;
        res += most_dangos(i);
    }
    cout << res << "\n";
    /*
    for (int t = 0; t < 2; t++) {
        const auto &arr = (t) ? vert : horiz;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cout << arr[i][j] << " \n"[j == m - 1];
            }
        }
    }
    */
}

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