#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
pair<int,int> pom[4] = {{0,1}, {0,-1}, {1, 0}, {-1, 0}};
pair<int,int> pom2[8] = {{1,1}, {1,-1}, {-1, 1}, {-1, -1}, {0,2}, {0,-2}, {2, 0}, {-2, 0}};
pair<int,int> pom3[4] = {{0,2}, {0,-2}, {2, 0}, {-2, 0}};
bool edge(int r, int c, int n, int m){
return (r==0 || r==n-1 || c==0 || c==m-1);
}
int getSum(int i, int n, int m, vvi& grid, vi& row, vi& col, vvb& taken){
int res = grid[row[i]][col[i]];
for(int p=0; p<4; p++){
int r = row[i] + pom[p].first,
c = col[i] + pom[p].second;
if(r<0 || r>=n || c<0 || c>=m) continue;
if(!taken[r][c])
res += grid[r][c];
taken[r][c] = true;
}
return res;
}
int getSumCount(int i, int n, int m, vvi& grid, vi& row, vi& col, vvb& taken, int& cnt, int& mr, int& mc){
int res = grid[row[i]][col[i]];
for(int p=0; p<4; p++){
int r = row[i] + pom[p].first,
c = col[i] + pom[p].second;
if(r<0 || r>=n || c<0 || c>=m) continue;
if(!taken[r][c]){
res += grid[r][c];
taken[r][c] = true;
cnt++;
if(mr == -1 || grid[r][c] < grid[mr][mc]){
mr = r; mc = c;
}
}
}
return res;
}
int solve(int n, int m, vvi& grid, int k, vi& row, vi& col, vvi& cellidx){
int res = 0;
vb solved(k, false);
vvb taken(n, vb(m, false));
for(int i=0; i<k; i++)
taken[row[i]][col[i]] = true;
for(int i=0; i<k; i++){
if(!solved[i]){
bool foundPair = false;
for(int r=-1; r<=1; r++){
for(int c=-1; c<=1; c++){
if(row[i]+r<0 || row[i]+r>=n || col[i]+c<0 || col[i]+c>=m)
continue;
if(r == 0 && c == 0)
continue;
int ci = cellidx[row[i]+r][col[i]+c];
if(ci == -1)
continue;
if(solved[ci] || foundPair)
return -1;
if(edge(row[i], col[i], n, m) || edge(row[ci], col[ci], n, m))
return -1;
solved[i] = solved[ci] = true;
res += getSum(i, n, m, grid, row, col, taken);
res += getSum(ci, n, m, grid, row, col, taken);
foundPair = true;
}
}
}
}
stack<int> st;
for(int i=0; i<k; i++){
if(!solved[i]){
int t = 0;
for(int p=0; p<4; p++){
int r = row[i] + pom[p].first,
c = col[i] + pom[p].second;
if(r<0 || r>=n || c<0 || c>=m || taken[r][c]) t++;
}
if(t > 1) return -1;
if(t == 1) st.push(i);
}
}
while(!st.empty()){
int i = st.top();
st.pop();
if(solved[i]) continue;
solved[i] = true;
res += grid[row[i]][col[i]];
int t = 0;
for(int p=0; p<4; p++){
int r = row[i] + pom[p].first,
c = col[i] + pom[p].second;
if(r<0 || r>=n || c<0 || c>=m) {
t++;
continue;
}
if(taken[r][c]) t++;
else {
taken[r][c] = true;
res += grid[r][c];
}
}
if(t > 1) return -1;
for(int p=0; p<8; p++){
int r = row[i] + pom2[p].first,
c = col[i] + pom2[p].second;
if(r<0 || r>=n || c<0 || c>=m) continue;
int ci = cellidx[r][c];
if(ci != -1) st.push(ci);
}
}
for(int i=0; i<k; i++){
if(!solved[i]){
vector<int> cmp;
queue<int> q;
q.push(i);
while(!q.empty()){
int v = q.front();
q.pop();
if(solved[v]) continue;
solved[v] = true;
cmp.push_back(v);
for(int p=0; p<4; p++){
int r = row[v] + pom3[p].first,
c = col[v] + pom3[p].second;
if(r<0 || r>=n || c<0 || c>=m) continue;
int ci = cellidx[r][c];
if(ci != -1) q.push(ci);
}
}
int cnt = 0, mr = -1, mc = -1;
for(int j : cmp)
res += getSumCount(j, n, m, grid, row, col, taken, cnt, mr, mc);
if(cnt > 3*cmp.size()){
res -= grid[mr][mc];
taken[mr][mc] = false;
} else if(cnt < 3*cmp.size())
return -1;
}
}
return res;
}
int main()
{
int n, m;
cin >> n >> m;
vvi grid(n, vi(m));
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
cin >> grid[i][j];
int k;
cin >> k;
vi row(k), col(k);
vvi cellidx(n, vi(m, -1));
for(int i=0; i<k; i++){
cin >> row[i] >> col[i];
cellidx[row[i]][col[i]] = i;
}
int res = solve(n, m, grid, k, row, col, cellidx);
if(res == -1) cout << "No\n";
else cout << res << '\n';
return 0;
}
Compilation message
covering.cpp: In function 'int solve(int, int, vvi&, int, vi&, vi&, vvi&)':
covering.cpp:148:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | if(cnt > 3*cmp.size()){
| ~~~~^~~~~~~~~~~~~~
covering.cpp:151:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | } else if(cnt < 3*cmp.size())
| ~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
9 ms |
460 KB |
Output is correct |
3 |
Correct |
25 ms |
1060 KB |
Output is correct |
4 |
Correct |
75 ms |
2640 KB |
Output is correct |
5 |
Correct |
247 ms |
8388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
8 ms |
548 KB |
Output is correct |
3 |
Correct |
25 ms |
1076 KB |
Output is correct |
4 |
Correct |
78 ms |
2748 KB |
Output is correct |
5 |
Correct |
245 ms |
8328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
8 ms |
544 KB |
Output is correct |
3 |
Correct |
25 ms |
1068 KB |
Output is correct |
4 |
Correct |
75 ms |
2756 KB |
Output is correct |
5 |
Correct |
269 ms |
8320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
13 ms |
828 KB |
Output is correct |
4 |
Correct |
9 ms |
660 KB |
Output is correct |
5 |
Correct |
27 ms |
1472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
9 ms |
460 KB |
Output is correct |
3 |
Correct |
25 ms |
1060 KB |
Output is correct |
4 |
Correct |
75 ms |
2640 KB |
Output is correct |
5 |
Correct |
247 ms |
8388 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
8 ms |
548 KB |
Output is correct |
8 |
Correct |
25 ms |
1076 KB |
Output is correct |
9 |
Correct |
78 ms |
2748 KB |
Output is correct |
10 |
Correct |
245 ms |
8328 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
12 |
Correct |
8 ms |
544 KB |
Output is correct |
13 |
Correct |
25 ms |
1068 KB |
Output is correct |
14 |
Correct |
75 ms |
2756 KB |
Output is correct |
15 |
Correct |
269 ms |
8320 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
13 ms |
828 KB |
Output is correct |
19 |
Correct |
9 ms |
660 KB |
Output is correct |
20 |
Correct |
27 ms |
1472 KB |
Output is correct |
21 |
Correct |
3 ms |
332 KB |
Output is correct |
22 |
Correct |
9 ms |
660 KB |
Output is correct |
23 |
Correct |
26 ms |
1436 KB |
Output is correct |
24 |
Correct |
79 ms |
3904 KB |
Output is correct |
25 |
Correct |
254 ms |
12228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
9 ms |
460 KB |
Output is correct |
3 |
Correct |
25 ms |
1060 KB |
Output is correct |
4 |
Correct |
75 ms |
2640 KB |
Output is correct |
5 |
Correct |
247 ms |
8388 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
8 ms |
548 KB |
Output is correct |
8 |
Correct |
25 ms |
1076 KB |
Output is correct |
9 |
Correct |
78 ms |
2748 KB |
Output is correct |
10 |
Correct |
245 ms |
8328 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
12 |
Correct |
8 ms |
544 KB |
Output is correct |
13 |
Correct |
25 ms |
1068 KB |
Output is correct |
14 |
Correct |
75 ms |
2756 KB |
Output is correct |
15 |
Correct |
269 ms |
8320 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
13 ms |
828 KB |
Output is correct |
19 |
Correct |
9 ms |
660 KB |
Output is correct |
20 |
Correct |
27 ms |
1472 KB |
Output is correct |
21 |
Correct |
1 ms |
256 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
0 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
3 ms |
332 KB |
Output is correct |
27 |
Correct |
9 ms |
660 KB |
Output is correct |
28 |
Correct |
26 ms |
1436 KB |
Output is correct |
29 |
Correct |
79 ms |
3904 KB |
Output is correct |
30 |
Correct |
254 ms |
12228 KB |
Output is correct |
31 |
Correct |
351 ms |
14356 KB |
Output is correct |
32 |
Correct |
251 ms |
12228 KB |
Output is correct |
33 |
Correct |
261 ms |
14668 KB |
Output is correct |
34 |
Correct |
251 ms |
12240 KB |
Output is correct |
35 |
Correct |
285 ms |
13252 KB |
Output is correct |