Submission #397944

#TimeUsernameProblemLanguageResultExecution timeMemory
397944nvujicaT-Covering (eJOI19_covering)C++14
0 / 100
60 ms94892 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second using namespace std; const int maxn = 1e6 + 10; int n, m, k, x, y, ans; vector <int> a[maxn]; vector <int> red[maxn]; vector <int> bio[maxn]; vector <int> ubr[maxn]; int dx[4] = {-2, 0, 0, 2}; int dy[4] = {0, -2, 2, 0}; queue <pair<int, int> > q; bool ok(int x, int y){ return x >= 0 && x < n && y >= 0 && y < m; } int bfs(int pocx, int pocy){ q.push({pocx, pocy}); bio[pocx][pocy] = 1; int cik = 0, sus = 0, mini = 1005, sum = 0; while(!q.empty()){ int x = q.front().fi; int y = q.front().se; q.pop(); for(int i = -1; i <= 1; i++){ for(int j = -1; j <= 1; j++){ if(i * j != 0) continue; int x2 = x + i; int y2 = y + j; if(!ok(x2, y2)) continue; if(ubr[x2][y2]) continue; sum += a[x2][y2]; if(i | j) mini = min(mini, a[x2][y2]); ubr[x2][y2] = 1; } } for(int i = -1; i <= 1; i++){ for(int j = -1; j <= 1; j++){ int x2 = x + i; int y2 = y + j; if(!ok(x2, y2)) continue; if(!red[x2][y2]) continue; if(bio[x2][y2]){ bio[x2][y2]++; continue; } sus++; bio[x2][y2] = 1; q.push({x2, y2}); } } for(int i = 0; i < 4; i++){ int x2 = x + dx[i]; int y2 = y + dy[i]; if(!ok(x2, y2)) continue; if(!red[x2][y2]) continue; if(bio[x2][y2]){ bio[x2][y2]++; continue; } bio[x2][y2] = 1; q.push({x2, y2}); } } if(cik + sus > 1) return -1; if(cik + sus == 1) return sum; return sum - mini; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ a[i].push_back(0); red[i].push_back(0); bio[i].push_back(0); ubr[i].push_back(0); } } for(int i = 0; i < n; i++){ a[i].push_back(0); for(int j = 0; j < m; j++){ cin >> a[i][j]; } } cin >> k; for(int i = 0; i < k; i++){ cin >> x >> y; red[x][y] = 1; } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(red[i][j] && !bio[i][j]){ //cout << "novi " << i << ' ' << j << endl; int sol = bfs(i, j); if(sol == -1){ cout << "No"; return 0; } else ans += sol; } } } cout << ans; 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...