Submission #641007

#TimeUsernameProblemLanguageResultExecution timeMemory
641007Tam_theguideT-Covering (eJOI19_covering)C++17
25 / 100
101 ms40292 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define pii pair<int, int> #define print(x) cout<<"["<<(x)<<"]" const pii E[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; const pii V[4] = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}}; const pii dt[4] = {{-2, 0}, {0, 2}, {2, 0}, {0, -2}}; int n , m , k; vector<vector<int>> a, dfs_vis; vector<vector<bool>> vis, red, cycle; vector<vector<vector<pii>>> adj; vector<vector<pii>> par; set<pii> cycle_hit; vector<pii> tree; void stop(){cout << "No"; exit(0);} bool boundary(int i, int j){return (i == 1 || i == n || j == 1 || j == m);} bool inside(int i, int j){return (1 <= i && i <= n && 1 <= j && j <= m);} void dfs(int i_, int j_, int i, int j){ if (dfs_vis[i][j] == 2) return; if (dfs_vis[i][j] == 1){ pii tmp = {i_, j_}; cycle[tmp.fi][tmp.se] = true; while (!(tmp.fi == i && tmp.se == j)){ pii xx = par[tmp.fi][tmp.se]; tmp.fi = xx.fi; tmp.se = xx.se; cycle[tmp.fi][tmp.se] = true; } return; } dfs_vis[i][j] = 1; par[i][j] = {i_, j_}; for (auto c: adj[i][j]){ if (c == par[i][j]) continue; dfs(i, j, c.fi, c.se); } dfs_vis[i][j] = 2; } int cnt; void dfs2(int i_, int j_, int i, int j){ cnt++; for (int t = 0; t < 4; t++){ int u = i + E[t].fi; int v = j + E[t].se; if (!vis[u][v]) tree.pb({u, v}); } dfs_vis[i][j] = 3; for (auto c: adj[i][j]){ if (!red[c.fi][c.se] || (c.fi == i_ && c.se == j_)) continue; dfs2(i, j, c.fi, c.se); } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; a.resize(n + 2, vector<int>(m + 2)); dfs_vis.resize(n + 2, vector<int>(m + 2, 0)); vis.resize(n + 2, vector<bool>(m + 2, false)); red.resize(n + 2, vector<bool>(m + 2, false)); cycle.resize(n + 2, vector<bool>(m + 2, false)); adj.resize(n + 2, vector<vector<pii>>(m + 2)); par.resize(n + 2, vector<pii>(m + 2)); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j]; cin >> k; for (int i = 1; i <= k; i++){ int u, v; cin >> u >> v; u++; v++; vis[u][v] = true; red[u][v] = true; if (boundary(u, v)){ for (int t = 0; t < 4; t++){ int u_ = u + E[t].fi; int v_ = v + E[t].se; if (inside(u_, v_)){ if (vis[u_][v_]) stop(); vis[u_][v_] = true; } } red[u][v] = false; } } // boundary-> done for (int u = 1; u <= n; u++) for (int v = 1; v <= m; v++){ if (red[u][v]){ for (int t = 1; t <= 2; t++){ int u_ = u + E[t].fi; int v_ = v + E[t].se; if (red[u_][v_]){ set<pii> tmp; tmp.insert({u, v}); tmp.insert({u_, v_}); for (int tt = 0; tt < 4; tt++){ int u__ = u_ + E[tt].fi; int v__ = v_ + E[tt].se; tmp.insert({u__, v__}); } for (int tt = 0; tt < 4; tt++){ int _u_ = u + E[tt].fi; int _v_ = v + E[tt].se; tmp.insert({_u_, _v_}); } if (tmp.size() != 8) stop(); for (auto c: tmp){ if (!(c.fi == u && c.se == v) && !(c.fi == u_ && c.se == v_) && vis[c.fi][c.se]) stop(); vis[c.fi][c.se] = true; } red[u][v] = red[u_][v_] = false; } } } } // edge -> done for (int u = 1; u <= n; u++) for (int v = 1; v <= m; v++){ if (red[u][v]){ for (int t = 1; t <= 2; t++){ int u_ = u + V[t].fi; int v_ = v + V[t].se; if (red[u_][v_]){ set<pii> tmp; tmp.insert({u, v}); tmp.insert({u_, v_}); for (int tt = 0; tt < 4; tt++){ int u__ = u_ + E[tt].fi; int v__ = v_ + E[tt].se; tmp.insert({u__, v__}); } for (int tt = 0; tt < 4; tt++){ int _u_ = u + E[tt].fi; int _v_ = v + E[tt].se; tmp.insert({_u_, _v_}); } if (tmp.size() != 8) stop(); for (auto c: tmp){ if (!(c.fi == u && c.se == v) && !(c.fi == u_ && c.se == v_) && vis[c.fi][c.se]) stop(); vis[c.fi][c.se] = true; } red[u][v] = red[u_][v_] = false; } } } } // vertice -> done for (int u = 1; u <= n; u++) for (int v = 1; v <= m; v++){ if (red[u][v]){ for (int t = 0; t < 4; t++){ int u_ = u + dt[t].fi; int v_ = v + dt[t].se; if (red[u_][v_]) adj[u][v].pb({u_, v_}); } } } for (int u = 1; u <= n; u++) for (int v = 1; v <= m; v++){ if (red[u][v] && dfs_vis[u][v] != 2){ dfs(0, 0, u, v); } } for (int u = 1; u <= n; u++) for (int v = 1; v <= m; v++) if (cycle[u][v]){ for (int t = 0; t < 4; t++){ int u_ = u + E[t].fi; int v_ = v + E[t].se; cycle_hit.insert({u_, v_}); } red[u][v] = false; } for (auto c: cycle_hit){ if (vis[c.fi][c.se]) stop(); vis[c.fi][c.se] = true; } // cycle -> done; for (int u = 1; u <= n; u++) for (int v = 1; v <= m; v++){ if (red[u][v] && dfs_vis[u][v] != 3){ tree.clear(); cnt = 0; dfs2(0, 0, u, v); sort(tree.begin(), tree.end()); tree.erase(unique(tree.begin(), tree.end()), tree.end()); int Tr = (int)tree.size(); if (Tr < 3 * cnt || Tr > 3 * cnt + 1) stop(); if (Tr == 3 * cnt + 1){ sort(tree.begin(), tree.end(), [&](pii x, pii y){ return a[x.fi][x.se] < a[y.fi][y.se]; }); for (int i = 1; i < tree.size(); i++) vis[tree[i].fi][tree[i].se] = true; }else{ for (auto c: tree) vis[c.fi][c.se] = true; } } } int ans = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (vis[i][j]) ans += a[i][j]; /* for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++){ if (vis[i][j]) print("x"); else print("o"); } cout << '\n'; } */ cout << ans; }

Compilation message (stderr)

covering.cpp: In function 'int main()':
covering.cpp:195:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |                     for (int i = 1; i < tree.size(); i++)
      |                                     ~~^~~~~~~~~~~~~
#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...