제출 #639564

#제출 시각아이디문제언어결과실행 시간메모리
639564Valaki2T-Covering (eJOI19_covering)C++14
100 / 100
172 ms31416 KiB
#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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...