oj.uz

Submission #639564

# Submission time Handle Problem Language Result Execution time Memory
639564 2022-09-10T15:56:05 Z Valaki2 T-Covering (eJOI19_covering) C++14
100 / 100
 172 ms 31416 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 7 ms 2316 KB Output is correct
4 Correct 19 ms 6324 KB Output is correct
5 Correct 62 ms 20040 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 3 ms 964 KB Output is correct
3 Correct 6 ms 2260 KB Output is correct
4 Correct 19 ms 6328 KB Output is correct
5 Correct 71 ms 20120 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 8 ms 2260 KB Output is correct
4 Correct 20 ms 6220 KB Output is correct
5 Correct 70 ms 20044 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 4 ms 1492 KB Output is correct
4 Correct 3 ms 980 KB Output is correct
5 Correct 8 ms 2736 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 7 ms 2316 KB Output is correct
4 Correct 19 ms 6324 KB Output is correct
5 Correct 62 ms 20040 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 3 ms 964 KB Output is correct
8 Correct 6 ms 2260 KB Output is correct
9 Correct 19 ms 6328 KB Output is correct
10 Correct 71 ms 20120 KB Output is correct
11 Correct 1 ms 456 KB Output is correct
12 Correct 5 ms 852 KB Output is correct
13 Correct 8 ms 2260 KB Output is correct
14 Correct 20 ms 6220 KB Output is correct
15 Correct 70 ms 20044 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 4 ms 1492 KB Output is correct
19 Correct 3 ms 980 KB Output is correct
20 Correct 8 ms 2736 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 2 ms 960 KB Output is correct
23 Correct 11 ms 2324 KB Output is correct
24 Correct 20 ms 6340 KB Output is correct
25 Correct 63 ms 20120 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 7 ms 2316 KB Output is correct
4 Correct 19 ms 6324 KB Output is correct
5 Correct 62 ms 20040 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 3 ms 964 KB Output is correct
8 Correct 6 ms 2260 KB Output is correct
9 Correct 19 ms 6328 KB Output is correct
10 Correct 71 ms 20120 KB Output is correct
11 Correct 1 ms 456 KB Output is correct
12 Correct 5 ms 852 KB Output is correct
13 Correct 8 ms 2260 KB Output is correct
14 Correct 20 ms 6220 KB Output is correct
15 Correct 70 ms 20044 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 4 ms 1492 KB Output is correct
19 Correct 3 ms 980 KB Output is correct
20 Correct 8 ms 2736 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 320 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 324 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 2 ms 960 KB Output is correct
28 Correct 11 ms 2324 KB Output is correct
29 Correct 20 ms 6340 KB Output is correct
30 Correct 63 ms 20120 KB Output is correct
31 Correct 172 ms 31416 KB Output is correct
32 Correct 71 ms 20824 KB Output is correct
33 Correct 76 ms 24272 KB Output is correct
34 Correct 66 ms 20564 KB Output is correct
35 Correct 91 ms 26736 KB Output is correct