Submission #639564

#	Time	Username	Problem	Language	Result	Execution time	Memory
639564		Valaki2	T-Covering (eJOI19_covering)	C++14	100 / 100	172 ms	31416 KiB

covering

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

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define vv(t) vector<vector<t> >
#define assi(t, t2) (t2).assign(1 + n + 1, vector<t> (1 + m + 1, 0))

const int inf0 = 1e3 + 42;

const vector<pii > dir4 {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
const vector<pii > dir2 {{2, 0}, {0, 2}, {0, -2}, {-2, 0}};
const vector<pii > dirdia {{1, 1}, {-1, 1}, {1, -1}, {-1, -1}};

int ans;

void no() {
    cout << "No\n";
    exit(0);
}

void answer() {
    cout << ans << "\n";
    exit(0);
}

struct dfs_ret {
    int adj_sum, adj_cnt, spec_cnt, min_leaf;
};

int n, m, k;
vv(int) val;
vv(bool) filled;
vv(int) center;
vector<pii > coords;
vector<bool> done;

int get_adj4_cnt(const pii &p) {
    int res = 0;
    for(const pii &d : dir4) {
        if(!filled[d.fi + p.fi][d.se + p.se]) {
            res++;
        }
    }
    return res;
}

inline pii add(pii a, pii b) {
    return mp(a.fi + b.fi, a.se + b.se);
}

inline pii between(pii a, pii b) {
    return mp((a.fi + b.fi) / 2, (a.se + b.se) / 2);
}

void try_extend(int first_idx) {
    if(done[first_idx]) {
        return;
    }
    vector<int> indices;
    indices.pb(first_idx);
    vector<pii> fills;
    while(!indices.empty()) {
        for(int idx : indices) {
            if(done[idx]) {
                continue;
            }
            int cnt = get_adj4_cnt(coords[idx]);
            if(cnt == 4) {
                continue;
            }
            if(cnt < 3) {
                no();
            }
            done[idx] = true;
            for(const pii &d : dir4) {
                pii nei = add(d, coords[idx]);
                if(!filled[nei.fi][nei.se]) {
                    filled[nei.fi][nei.se] = true;
                    ans += val[nei.fi][nei.se];
                    fills.pb(nei);
                }
            }
        }
        indices.clear();
        for(pii cur : fills) {
            for(const pii &d : dir4) {
                pii nei = add(d, cur);
                if(center[nei.fi][nei.se] && !done[center[nei.fi][nei.se]]) {
                    indices.pb(center[nei.fi][nei.se]);
                }
            }
        }
        fills.clear();
    }
}

dfs_ret dfs(int idx, int par) {
    dfs_ret res = {0, 0, 1, inf0};
    const pii &ci = coords[idx];
    done[idx] = true;
    for(const pii &d : dir2) {
        pii nei = add(ci, d);
        pii bet = between(ci, nei);
        if(center[nei.fi][nei.se]) {
            if(done[center[nei.fi][nei.se]]) {
                res.adj_cnt++;
                res.adj_sum += val[bet.fi][bet.se];
                res.min_leaf = min(res.min_leaf, val[bet.fi][bet.se]);
            } else {
                res.adj_cnt++;
                res.adj_sum += val[bet.fi][bet.se];
                res.min_leaf = min(res.min_leaf, val[bet.fi][bet.se]);
                dfs_ret other_res = dfs(center[nei.fi][nei.se], idx);
                res.adj_sum += other_res.adj_sum;
                res.adj_cnt += other_res.adj_cnt;
                res.spec_cnt += other_res.spec_cnt;
                res.min_leaf = min(res.min_leaf, other_res.min_leaf);
            }
        } else {
            res.adj_cnt += 2;
            res.adj_sum += 2 * val[bet.fi][bet.se];
            res.min_leaf = min(res.min_leaf, val[bet.fi][bet.se]);
        }
    }
    return res;
}

void solve() {
    // init
    cin >> n >> m;
    assi(int, val);
    assi(bool, filled);
    assi(int, center);
    for(int i = 0; i <= n; i++) {
        filled[i][0] = filled[i][m + 1] = true;
    }
    for(int j = 0; j <= m; j++) {
        filled[0][j] = filled[n + 1][j] = true;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> val[i][j];
        }
    }
    cin >> k;
    coords.assign(1 + k, mp(0, 0));
    done.assign(1 + k, false);
    for(int i = 1; i <= k; i++) {
        pii &p = coords[i];
        cin >> p.fi >> p.se;
        p.fi++;
        p.se++;
        ans += val[p.fi][p.se];
        filled[p.fi][p.se] = true;
        center[p.fi][p.se] = i;
    }
    // try_extend everywhere
    for(int i = 1; i <= k; i++) {
        try_extend(i);
    }
    // diagonal pairs
    for(int i = 1; i <= k; i++) {
        if(done[i]) {
            continue;
        }
        const pii &ci = coords[i];
        for(const pii &d1 : dirdia) {
            const pii &nei = add(ci, d1);
            // ? the neighbour might have been done already
            if(center[nei.fi][nei.se]) {
                vector<pii> empty_list = {{nei.fi, nei.se + d1.se}, {nei.fi + d1.fi, nei.se}};
                for(const pii &d2 : dir4) {
                    empty_list.pb(add(ci, d2));
                }
                for(const pii &p : empty_list) {
                    if(filled[p.fi][p.se]) {
                        no();
                    }
                    filled[p.fi][p.se] = true;
                    ans += val[p.fi][p.se];
                }
                done[center[nei.fi][nei.se]] = true;
                done[i] = true;
            }
        }
    }
    // try_extend everywhere
    for(int i = 1; i <= k; i++) {
        try_extend(i);
    }
    // short code for a subtask
    /*
    {
        for(int i = 1; i <= k; i++) {
            if(!done[i]) {
                const pii &ci = coords[i];
                vector<int> tmp;
                for(const pii &d : dir4) {
                    tmp.pb(val[ci.fi + d.fi][ci.se + d.se]);
                }
                sort(tmp.begin(), tmp.end());
                ans += tmp[1] + tmp[2] + tmp[3];
            }
        }
    }
    */
    // dfs
    for(int i = 1; i <= k; i++) {
        if(done[i]) {
            continue;
        }
        dfs_ret res = dfs(i, -1);
        res.adj_cnt /= 2;
        res.adj_sum /= 2;
        res.spec_cnt *= 3;
        if(res.spec_cnt > res.adj_cnt) {
            no();
        }
        if(res.spec_cnt == res.adj_cnt) {
            ans += res.adj_sum;
        } else {
            ans += res.adj_sum - res.min_leaf;
        }
    }
    answer();
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

/*
5 5
1 5 1 5 1
5 1 5 1 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
4
1 1
1 3
3 1
3 3
*/

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