Submission #211273

#	Time	Username	Problem	Language	Result	Execution time	Memory
211273		shart23	Dango Maker (JOI18_dango_maker)	C++14	0 / 100	128 ms	262144 KiB

dango_maker

#include <bits/stdc++.h>

#define int long long
#define endl "\n"

using namespace std;

const int MAXN = 3000;
vector<int> vin[MAXN][MAXN];
vector<int> g[MAXN * MAXN];
int used[MAXN * MAXN];
int nn[MAXN * MAXN];
int sm[MAXN * MAXN];
set<int> g2[MAXN * MAXN];
pair<int, int> dp[MAXN * MAXN];

void dfs3(int v, int p) {
    used[v] = 3;
    if (sm[v] > 1) {
        dp[v].first = sm[v] / 2;
        dp[v].second = sm[v] / 2;
    } else {
        dp[v].first = 1;
    }
    for (int u : g2[v]) {
        if (u != p && used[u] != 3) {
            dfs3(u, v);
            dp[v].first += dp[u].second;
            dp[v].second += max(dp[u].first, dp[u].second);
        }
    }
}

bool is_edge(int v, int u, int p) {
    for (auto x : g[v]) {
        if (x == u && x != p) {
            return true;
        }
    }
    return false;
}

bool check(int v) {
    for (int i = 0; i < g[v].size(); i++) {
        for (int j = i + 1; j < g[v].size(); j++) {
            for (int u : g[g[v][i]]) {
                if (is_edge(g[v][j], u, v)) {
                    return true;
                }
            }
        }
    }
    return false;
}

void dfs(int v, vector<int> &comp) {
    comp.push_back(v);
    used[v] = 1;
    for (int u : g[v]) {
        if (!used[u]) {
            dfs(u, comp);
        }
    }
}

void dfs2(int v, set<int> &in_c, int num) {
    used[v] = 2;
    nn[v] = num;
    if (in_c.find(v) == in_c.end()) {
        return;
    }
    for (int u : g[v]) {
        if (used[u] != 2) {
            dfs2(u, in_c, num);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> arr(n);
    for (auto &x : arr) {
        cin >> x;
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i <= n - 3) {
                if (arr[i][j] == 'R' && arr[i + 1][j] == 'G' && arr[i + 2][j] == 'W') {
                    vin[i][j].push_back(cnt);
                    vin[i + 1][j].push_back(cnt);
                    vin[i + 2][j].push_back(cnt);
                    cnt++;
                }
            }
            if (j <= m - 3) {
                if (arr[i][j] == 'R' && arr[i][j + 1] == 'G' && arr[i][j + 2] == 'W') {
                    vin[i][j].push_back(cnt);
                    vin[i][j + 1].push_back(cnt);
                    vin[i][j + 2].push_back(cnt);
                    cnt++;
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (auto v : vin[i][j]) {
                for (auto u : vin[i][j]) {
                    if (v != u) {
                        g[v].push_back(u);
                    }
                }
            }
        }
    }
    int cnt2 = 0;
    for (int i = 0; i < cnt; i++) {
        if (!used[i]) {
            vector<int> comp;
            dfs(i, comp);
            set<int> in_c;
            for (auto x : comp) {
                if (check(x)) {
                    in_c.insert(x);
                }
            }
            for (auto x : comp) {
                if (used[x] != 2) {
                    dfs2(x, in_c, cnt2);
                    cnt2++;
                }
            }
        }
    }
    for (int i = 0; i < cnt; i++) {
        sm[nn[i]]++;
        for (int u : g[i]) {
            if (nn[u] != nn[i]) {
                g2[nn[i]].insert(nn[u]);
            }
        }
    }
    int res = 0;
    for (int i = 0; i < cnt2; i++) {
        if (used[i] != 3) {
            dfs3(i, -1);
            res += max(dp[i].first, dp[i].second);
        }
    }
    cout << res << endl;
}

Compilation message (stderr)

dango_maker.cpp: In function 'bool check(long long int)':
dango_maker.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++) {
                     ~~^~~~~~~~~~~~~
dango_maker.cpp:45:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i + 1; j < g[v].size(); j++) {
                             ~~^~~~~~~~~~~~~

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