Submission #1312722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312722		penguin133	T-Covering (eJOI19_covering)	C++20	55 / 100	167 ms	38516 KiB

covering

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};

void die(){
    cout << "No";
    exit(0);
}
int n, m; 
int par[1000005], sz[1000005], mn[1000005], s[1000005];
ll sm[1000005];

inline int conv(int x, int y) {
    return (x - 1) * m + y;
}

int getr(int x) {return par[x] == x ? x : par[x] = getr(par[x]);}

bool merge(int a, int b) {
    a = getr(a); b = getr(b);
    if (a == b) return 0;
    par[b] = a;
    sz[a] += sz[b];
    sm[a] += sm[b];
    mn[a] = min(mn[a], mn[b]);
    s[a] += s[b];
    return 1;
}

int main() {
	cin >> n >> m;
    ll a[n + 1][m + 1], b[n + 1][m + 1] = {0}, vis[n + 1][m + 1] = {0};
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    int k; cin >> k;
    while (k--) {
        int x, y; cin >> x >> y;
        x++; y++;
        if (b[x][y]) {
            cout << "No";
            return 0;
        }
        b[x][y] = 1;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!b[i][j]) continue;
            ans += a[i][j];
            int c = 0;
            for (int aa = 0; aa < 8; aa++) {
                int x1 = i + dx[aa], y1 = j + dy[aa];
                if (x1 < 1 || x1 > n || y1 < 1 || y1 > m) continue;
                if (b[x1][y1]) c++;
            }
            if (c >= 2) {
                cout << "No";
                return 0;
            }
            if (c) {
                for (int aa = 0; aa < 8; aa++) {
                    int x1 = i + dx[aa], y1 = j + dy[aa];
                    if (x1 < 1 || x1 > n || y1 < 1 || y1 > m) continue;
                    if (b[x1][y1]) {
                        if (aa <= 1 || aa == 7) {
                            if (j == 1 || j == m || i == n) die();
                            ans += a[i][j - 1] + a[i][j + 1] + a[i + 1][j];
                            vis[i][j - 1] = vis[i][j + 1] = vis[i + 1][j] = 1;
                        }
                        else if (aa == 2) {
                            if (j == 1 || i == 1 || i == n) die();
                            ans += a[i - 1][j] + a[i][j - 1] + a[i + 1][j];
                            vis[i - 1][j] = vis[i][j - 1] = vis[i + 1][j] = 1;
                        }
                        else if (aa >= 3 && aa <= 5) {
                            if (i == 1 || j == 1 || j == m) die();
                            ans += a[i - 1][j] + a[i][j - 1] + a[i][j + 1];
                            vis[i - 1][j] = vis[i][j - 1] = vis[i][j + 1] = 1;
                        }
                        else {
                            if (i == n || i == 1 || j == m) die();
                            ans += a[i - 1][j] + a[i + 1][j] + a[i][j + 1];
                            vis[i - 1][j] = vis[i + 1][j] = vis[i][j + 1] = 1;
                        }
                    }
                }
                vis[i][j] = 1;
            }
        }
    }
    //cout << ans << '\n';
    queue <pair <int, int> > q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (vis[i][j] || !b[i][j]) continue;
            int cnt = 0;
            for (int aa = 0; aa < 8; aa += 2) {
                int x1 = i + dx[aa], y1 = j + dy[aa];
                if (x1 < 1 || x1 > n || y1 < 1 || y1 > m) continue;
                if (vis[x1][y1]) continue;
                cnt++;
            }
            if (cnt < 3) die();
            if (cnt == 3) q.push({i, j});
        }
    }
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        if (vis[x][y]) continue;
        vis[x][y] = 1;
        for (int aa = 0; aa < 8; aa += 2) {
            int x1 = x + dx[aa], y1 = y + dy[aa];
            if (x1 < 1 || x1 > n || y1 < 1 || y1 > m) continue;
            if (vis[x1][y1]) continue;
            ans += a[x1][y1];
            int x2 = x1 + dx[aa], y2 = y1 + dy[aa];
            if (x2 < 1 || x2 > n || y2 < 1 || y2 > m) continue;
            if (vis[x2][y2]) continue;
            if (b[x2][y2]) q.push({x2, y2});
        }
    }
    //cout << ans << '\n';
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            par[conv(i, j)] = conv(i, j);
            if (!vis[i][j] && b[i][j]) {
                mn[conv(i, j)] = min({a[i - 1][j], a[i + 1][j], a[i][j - 1], a[i][j + 1]});
                sm[conv(i, j)] = a[i - 1][j] + a[i + 1][j] + a[i][j - 1] + a[i][j + 1];
                sz[conv(i, j)] = 4;
                s[conv(i, j)] = 1;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (vis[i][j] || !b[i][j]) continue;
            if (j > 2 && b[i][j - 2] && !vis[i][j - 2]) {
                bool suc = merge(conv(i, j - 2), conv(i, j));
                sz[getr(conv(i, j))]--;
                sm[getr(conv(i, j))] -= a[i][j - 1];
            }
            if (i > 2 && b[i - 2][j] && !vis[i - 2][j]) {
                bool suc = merge(conv(i - 2, j), conv(i, j));
                if (1) { 
                    sz[getr(conv(i, j))]--;
                    sm[getr(conv(i, j))] -= a[i - 1][j];
                }
            }
        }
    }
    set <int> ss;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (vis[i][j] || !b[i][j]) continue;
            if (ss.find(getr(conv(i, j))) != ss.end()) continue;
            int r = getr(conv(i, j));
            if (3 * s[r] > sz[r]) die();
            if (3 * s[r] < sz[r]) {
                assert(3 * s[r] + 1 == sz[r]);
                //cout << "hi\n";
                ans += sm[r] - mn[r];
            }
            else ans += sm[r];
            ss.insert(r);
        }
    }
    cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 15
• Subtask 6: 20 / 20
• Subtask 7: 0 / 30