Submission #1125242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125242		eysbutno	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	291 ms	327680 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<bool> vis(timer);
    vector<int> col(timer, -1);
    const auto most_dangos = [&](int src) -> int {
        array<int, 2> res = {0, 0};
        int cur = 0;
        const auto dfs = [&](int u, int p, auto &&self) -> void {
            // if (cur == 0) assert(!vis[u]);
            vis[u] = true;
            res[cur] += col[u];
            for (int v : adj[u]) {
                if (v == p) { continue; }
                col[v] = !col[u];
                self(v, u, self);
            }
        };
        col[src] = 0;
        dfs(src, -1, dfs);
        
        cur = 1;
        col[src] = 1;
        dfs(src, -1, dfs);

        return max(res[0], res[1]);
    };
    int res = 0;
    for (int i = 0; i < timer; i++) {
        if (vis[i]) 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];
            }
        }
    }
    */
}

/**
 * grid of dangos
 * 
 * choose 3 consecutive dangos (l->r, or t->b)
 * and string them together
 * 
 * must be RED, GREEN, WHITE
 * 
 * ok, first there are O(nm) possible dangos.
 * 
 * we need to think of the relations between the dangos.
 * how does adding one dango affect another?
 * 
 * ok, so adding one dango prevents any dangoes that 
 * go thru its cells to be placed.
 * 
 * relations between dangos => we have a graph!
 * 
 * adjacent dangoes that go thru can't work
 * 
 * => like a bipartite graph
 * => for each component, we want max bipartite matching
 * 
 * ok good stuff
 * 
 * is the graph acyclic? i don't think it is because like,
 * dangos can only go l->r and u->d, which means you can't go baackwards
 * or anything funny
 * 
 * 
 */

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