제출 #629670

#제출 시각아이디문제언어결과실행 시간메모리
629670lovrotT-Covering (eJOI19_covering)C++11
100 / 100
175 ms46632 KiB
#include <bits/stdc++.h> #include <unistd.h> #define X first #define Y second #define ll long long #define pii pair<int, int> #define pb push_back #define vec vector #define pri(i, poc, n, pov) for(int i = (int) poc; i < (int) n; i += (int) pov) #define od(i, poc, n, pov) for(int i = (int) poc; i > (int) n; i -= (int) pov) using namespace std; const int INF = 1e9; const int lx[8] = {1, -1, 0, 0, -1, 1, 1, -1}; const int ly[8] = {0, 0, 1, -1, -1, 1, -1, 1}; const int N = 1e6 + 10; int n, m, q; int cdeg[N], vis[N]; vec<vec<int>> mat, spec; vec<vec<bool>> bio, xp; vec<pii> vx; vec<int> g[N]; void fail(){ cout << "No\n"; exit(0); } void success(){ int ans = 0; pri(i, 1, n + 1, 1) pri(j, 1, m + 1, 1) ans += (bio[i][j] ? mat[i][j] : 0); cout << ans << "\n"; } void markPlus(int x, int y){ bio[x][y] = 1; pri(i, 0, 4, 1) bio[x + lx[i]][y + ly[i]] = 1; } void countBan(int x, int y){ int cnt = bio[x][y]; pri(i, 0, 4, 1){ cnt += bio[x + lx[i]][y + ly[i]]; } if(cnt > 1) fail(); } void tryPlace(int x, int y){ countBan(x, y); markPlus(x, y); } pii findLow(int x, int y){ pii ret; int mn = INF; pri(i, 0, 4, 1) if(mat[x + lx[i]][y + ly[i]] < mn){ mn = mat[x + lx[i]][y + ly[i]]; ret = {x + lx[i], y + ly[i]}; } return ret; } //+ vec<vec<int>> createMat(int h, int w){ vec<vec<int>> ret; pri(i, 0, h, 1){ vec<int> line; pri(j, 0, w, 1) line.pb(0); ret.pb(line); } return ret; } //+ vec<vec<bool>> createBio(int h, int w){ vec<vec<bool>> ret; pri(i, 0, h, 1){ vec<bool> line; pri(j, 0, w, 1) line.pb(0); ret.pb(line); } return ret; } bool isCyc(int u, int p){ if(vis[u]) return true; vis[u] = true; for(int v : g[u]){ if(v != p && vis[v]){ vis[u] = false; return true; } if(v == p) continue; if(isCyc(v, u)) { vis[u] = false; return true; } } vis[u] = false; return false; } pii rek2(int u){ pii ret = {1, g[u].size()}; vis[u] = true; markPlus(vx[u].X, vx[u].Y); for(int v : g[u]){ //cout << u << " " << v << "\n"; if(vis[v]) continue; pii res = rek2(v); ret.X += res.X; ret.Y += res.Y; } return ret; } pii rek(int u){ if(vis[u]) return {0, 0}; vis[u] = true; tryPlace(vx[u].X, vx[u].Y); pii p = findLow(vx[u].X, vx[u].Y); for(int v : g[u]){ if(vis[v]) continue; pii res = rek(v); if(mat[p.X][p.Y] > mat[res.X][res.Y]) swap(p, res); } return p; } void init(){ cin >> n >> m; bio = createBio(n + 2, m + 2); xp = createBio(n + 2, m + 2); mat = createMat(n + 2, m + 2); spec = createMat(n + 2, m + 2); mat[0][0] = INF; pri(i, 1, n + 1, 1) pri(j, 1, m + 1, 1) cin >> mat[i][j]; // pri(i, 0, n + 2, 1) // xp[i][0] = xp[i][m + 1] = 1; // pri(i, 0, m + 2, 1){ // xp[0][i] = xp[n + 1][i] = 1; // } cin >> q; pri(i, 0, q, 1){ int x, y; cin >> x >> y; x++; y++; vx.pb({x, y}); xp[x][y] = true; spec[x][y] = i + 1; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); init(); // cout << "da\n"; //close edges pri(i, 0, q, 1){ int x = vx[i].X; int y = vx[i].Y; pri(j, 0, 8, 1){ int nx = x + lx[j]; int ny = y + ly[j]; if(xp[nx][ny] || (nx == 0 && ny == y) || (nx == n + 1 && ny == y) || (ny == 0 && nx == x) || (ny == m + 1 && nx == x)){ cdeg[i]++; } if(j < 4){ nx += lx[j]; ny += ly[j]; if(nx > 0 && nx < n + 1 && ny > 0 && ny < m + 1 && spec[nx][ny]) g[i].pb(spec[nx][ny] - 1); } } // cout << i << " " << cdeg[i] << "\n"; if(cdeg[i] > 1) fail(); if(cdeg[i] == 1){ vis[i] = true; markPlus(x, y); } } //cover groups touching close-pairs pri(i, 0, q, 1){ if(cdeg[i] == 1){ for(int v : g[i]){ if(cdeg[v] == 1) fail(); rek(v); } } } pri(i, 0, q, 1){ if(vis[i]) continue; bool res = isCyc(i, -1); if(!res){ pii p = rek(i); bio[p.X][p.Y] = false; } else { pii ret = rek2(i); if(ret.X - ret.Y / 2 < 0) fail(); } } // pri(i, 1, n + 1, 1) // pri(j, 1, m + 1, 1) // cout << bio[i][j] << " \n"[j == m]; success(); return 0; }
#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...