#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 <vector <int> > a;
vector <vector <int> > red;
vector <vector <int> > bio;
vector <vector <int> > ubr;
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, vani = 0, mini = 1005, sum = 0;
while(!q.empty()){
int x = q.front().fi;
int y = q.front().se;
q.pop();
cik += bio[x][y] - 1;
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)){
vani++;
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});
}
}
//cout << cik << ' ' << sus << ' ' << vani << endl;
if(cik + sus + vani > 1) return -1;
if(cik + sus + vani == 1) return sum;
return sum - mini;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
vector <int> v(m, 0);
for(int i = 0; i < n; i++){
a.push_back(v);
red.push_back(v);
bio.push_back(v);
ubr.push_back(v);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> x;
a[i][j] = x;
}
}
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]){
int sol = bfs(i, j);
if(sol == -1){
cout << "No";
return 0;
}
else ans += sol;
}
}
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
460 KB |
Output is correct |
2 |
Correct |
3 ms |
844 KB |
Output is correct |
3 |
Correct |
9 ms |
1836 KB |
Output is correct |
4 |
Correct |
29 ms |
5148 KB |
Output is correct |
5 |
Correct |
89 ms |
19856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
464 KB |
Output is correct |
2 |
Correct |
3 ms |
844 KB |
Output is correct |
3 |
Correct |
9 ms |
1936 KB |
Output is correct |
4 |
Correct |
27 ms |
5068 KB |
Output is correct |
5 |
Correct |
90 ms |
19908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
3 ms |
848 KB |
Output is correct |
3 |
Correct |
9 ms |
1868 KB |
Output is correct |
4 |
Correct |
26 ms |
5156 KB |
Output is correct |
5 |
Correct |
88 ms |
19852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
5 ms |
1100 KB |
Output is correct |
4 |
Correct |
3 ms |
716 KB |
Output is correct |
5 |
Correct |
9 ms |
1868 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 |
1 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 |
2 ms |
460 KB |
Output is correct |
2 |
Correct |
3 ms |
844 KB |
Output is correct |
3 |
Correct |
9 ms |
1836 KB |
Output is correct |
4 |
Correct |
29 ms |
5148 KB |
Output is correct |
5 |
Correct |
89 ms |
19856 KB |
Output is correct |
6 |
Correct |
2 ms |
464 KB |
Output is correct |
7 |
Correct |
3 ms |
844 KB |
Output is correct |
8 |
Correct |
9 ms |
1936 KB |
Output is correct |
9 |
Correct |
27 ms |
5068 KB |
Output is correct |
10 |
Correct |
90 ms |
19908 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
3 ms |
848 KB |
Output is correct |
13 |
Correct |
9 ms |
1868 KB |
Output is correct |
14 |
Correct |
26 ms |
5156 KB |
Output is correct |
15 |
Correct |
88 ms |
19852 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
5 ms |
1100 KB |
Output is correct |
19 |
Correct |
3 ms |
716 KB |
Output is correct |
20 |
Correct |
9 ms |
1868 KB |
Output is correct |
21 |
Correct |
2 ms |
460 KB |
Output is correct |
22 |
Correct |
3 ms |
972 KB |
Output is correct |
23 |
Correct |
9 ms |
2328 KB |
Output is correct |
24 |
Correct |
26 ms |
6348 KB |
Output is correct |
25 |
Correct |
86 ms |
19860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
460 KB |
Output is correct |
2 |
Correct |
3 ms |
844 KB |
Output is correct |
3 |
Correct |
9 ms |
1836 KB |
Output is correct |
4 |
Correct |
29 ms |
5148 KB |
Output is correct |
5 |
Correct |
89 ms |
19856 KB |
Output is correct |
6 |
Correct |
2 ms |
464 KB |
Output is correct |
7 |
Correct |
3 ms |
844 KB |
Output is correct |
8 |
Correct |
9 ms |
1936 KB |
Output is correct |
9 |
Correct |
27 ms |
5068 KB |
Output is correct |
10 |
Correct |
90 ms |
19908 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
3 ms |
848 KB |
Output is correct |
13 |
Correct |
9 ms |
1868 KB |
Output is correct |
14 |
Correct |
26 ms |
5156 KB |
Output is correct |
15 |
Correct |
88 ms |
19852 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
5 ms |
1100 KB |
Output is correct |
19 |
Correct |
3 ms |
716 KB |
Output is correct |
20 |
Correct |
9 ms |
1868 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 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 |
2 ms |
460 KB |
Output is correct |
27 |
Correct |
3 ms |
972 KB |
Output is correct |
28 |
Correct |
9 ms |
2328 KB |
Output is correct |
29 |
Correct |
26 ms |
6348 KB |
Output is correct |
30 |
Correct |
86 ms |
19860 KB |
Output is correct |
31 |
Correct |
124 ms |
20172 KB |
Output is correct |
32 |
Correct |
84 ms |
19780 KB |
Output is correct |
33 |
Correct |
101 ms |
22200 KB |
Output is correct |
34 |
Correct |
86 ms |
19668 KB |
Output is correct |
35 |
Correct |
104 ms |
20224 KB |
Output is correct |