Submission #995965

#	Time	Username	Problem	Language	Result	Execution time	Memory
995965		yanb	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	1 ms	604 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<long long, long long>

struct Stick {
    int x, y;
    bool r;
    vector<pii> pos;

    Stick(int x, int y, bool r) {
        this->x = x;
        this->y = y;
        this->r = r;
        if (r) {
            pos.push_back({x, y});
            pos.push_back({x, y + 1});
            pos.push_back({x, y + 2});
        } else {
            pos.push_back({x, y});
            pos.push_back({x + 1, y});
            pos.push_back({x + 2, y});
        }
    }

    bool operator&(const Stick &s) const {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (pos[i] == s.pos[j]) return 1;
            }
        }
        return 0;
    }
};

int df0, df1;

void dfs(int v, int cc, vector<vector<int>> &g, vector<int> &col) {
    if (col[v] != -1) return;
    col[v] = cc;
    if (cc == 0) df0++;
    else df1++;

    for (int u : g[v]) {
        dfs(u, (cc ? 0 : 1), g, col);
    }
}

int solve(int n, vector<Stick> &a) {
    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i] & a[j]) {
                g[i].push_back(j);
            }
        }
    }

    int ans = 0;
    vector<int> col(n, -1);
    for (int i = 0; i < n; i++) {
        df0 = df1 = 0;
        dfs(i, 0, g, col);
        ans += max(df0, df1);
    }
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    vector<Stick> cand;
    for (int i = 0; i < n - 2; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W') cand.push_back(Stick(i, j, 0));
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m - 2; j++) {
            if (a[i][j] == 'R' && a[i][j + 1] == 'G' && a[i][j + 2] == 'W') cand.push_back(Stick(i, j, 1));
        }
    }

    cout << solve(cand.size(), cand) << "\n";
}   

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