// In the name of Allah
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define debug(x) cerr << #x << ": " << x << endl;
#define kill(x) cout << x << '\n', exit(0);
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
int n, m, k;
ll output;
const int maxn = 1e6 + 3;
int a[maxn];
int mark[maxn];
int col[maxn]; int c = 1;
pii cl[maxn];
queue<pii> qu; vector<pair<ll, pii>> vc;
int GI(int i, int j) {
return (i * m + j);
}
void solve1(int x, int y) {
int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1};
if (mark[GI(x, y)] == 2) return ;
qu.push(Mp(x, y));
while (!qu.empty()) {
int r = 0;
x = qu.front().F, y = qu.front().S;
qu.pop();
for (int x1 : {x - 1, x + 1}) {
for (int y1 : {y - 1, y + 1}) {
if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && mark[GI(x1, y1)] == 1) {
r -= 1;
}
}
}
if (r == -1) {
mark[GI(x, y)] = 2;
output += a[GI(x, y)];
vector<pii> vc;
for (int T = 0; T < 4; T++) {
int x1 = x + dx[T], y1 = y + dy[T];
if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !mark[GI(x1, y1)]) {
mark[GI(x1, y1)] = 2;
output += a[GI(x1, y1)];
vc.pb(Mp(x1, y1));
}
}
int xr = -1, yr = -1;
for (int x1 : {x - 1, x + 1}) {
for (int y1 : {y - 1, y + 1}) {
if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && mark[GI(x1, y1)] == 1) {
xr = x1; yr = y1;
break;
}
}
if (xr != -1) break;
}
mark[GI(xr, yr)] = 2;
output += a[GI(xr, yr)];
for (int T = 0; T < 4; T++) {
int x1 = xr + dx[T], y1 = yr + dy[T];
if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !mark[GI(x1, y1)]) {
mark[GI(x1, y1)] = 2;
output += a[GI(x1, y1)];
vc.pb(Mp(x1, y1));
}
}
if (len(vc) != 6) {
kill("No");
}
for (auto f : vc) {
int x1 = f.F, y1 = f.S;
for (int R = 0; R < 4; R++) {
int x2 = x1 + dx[R], y2 = y1 + dy[R];
if (x2 >= 0 && x2 < n && y2 >= 0 && y2 < m && mark[GI(x2, y2)] == 1) {
qu.push(Mp(x2, y2));
}
}
}
continue;
}
else if (r < -1) {
kill("No");
}
r = 0;
for (int T = 0; T < 4; T++) {
int x1 = x + dx[T], y1 = y + dy[T];
if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !mark[GI(x1, y1)]) {
r += 1;
}
}
if (r < 3) {
kill("No");
}
else if (r == 3) {
mark[GI(x, y)] = 2;
output += a[GI(x, y)];
vector<pii> vc;
for (int T = 0; T < 4; T++) {
int x1 = x + dx[T], y1 = y + dy[T];
if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !mark[GI(x1, y1)]) {
mark[GI(x1, y1)] = 2;
output += a[GI(x1, y1)];
vc.pb(Mp(x1, y1));
}
}
for (auto f : vc) {
int x1 = f.F, y1 = f.S;
for (int R = 0; R < 4; R++) {
int x2 = x1 + dx[R], y2 = y1 + dy[R];
if (x2 >= 0 && x2 < n && y2 >= 0 && y2 < m && mark[GI(x2, y2)] == 1) {
qu.push(Mp(x2, y2));
}
}
}
}
}
}
void solve2(int x, int y) {
int dx[4] = {-2, 2, 0, 0}; int dy[4] = {0, 0, -2, 2};
int rx[4] = {-1, 1, 0, 0}; int ry[4] = {0, 0, -1, 1};
if (mark[GI(x, y)] == 2 || col[GI(x, y)] != 0) return ;
col[GI(x, y)] = c;
qu.push(Mp(x, y));
int deg = 0, l = 0;
vc.clear();
while (!qu.empty()) {
x = qu.front().F, y = qu.front().S;
output += a[GI(x, y)];
l += 1;
qu.pop();
for (int T = 0; T < 4; T++) {
int x1 = x + rx[T], y1 = y + ry[T];
if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !mark[GI(x1, y1)]) {
mark[GI(x1, y1)] = 2;
vc.pb(Mp(a[GI(x1, y1)], Mp(x1, y1)));
}
}
for (int T = 0; T < 4; T++) {
int x1 = x + dx[T], y1 = y + dy[T];
if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && mark[GI(x1, y1)] == 1) {
deg += 1;
if (col[GI(x1, y1)] == 0) {
col[GI(x1, y1)] = c;
qu.push(Mp(x1, y1));
}
}
}
}
int eds_num = deg / 2;
sort(all(vc), greater<pair<ll, pii>>());
if (eds_num == l) {
if (len(vc) < 3 * l) kill("No");
for (auto f : vc) {
output += f.F;
}
}
else if (eds_num == l - 1) {
if (len(vc) < 3 * l) kill("No");
if (len(vc) == 3 * l + 1) {
auto f = vc[len(vc) - 1];
int x1 = f.S.F, y1 = f.S.S;
mark[GI(x1, y1)] = 0;
vc.pop_back();
}
for (auto f : vc) {
output += f.F;
}
}
else {
kill("No");
}
c++;
return ;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[GI(i, j)];
}
}
int k;
cin >> k;
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
cl[i].F = x; cl[i].S = y;
mark[GI(x, y)] = 1;
}
for (int i = 0; i < k; i++) {
solve1(cl[i].F, cl[i].S);
}
for (int i = 0; i < k; i++) {
solve2(cl[i].F, cl[i].S);
}
cout << output << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
748 KB |
Output is correct |
3 |
Correct |
7 ms |
1684 KB |
Output is correct |
4 |
Correct |
20 ms |
4656 KB |
Output is correct |
5 |
Correct |
71 ms |
14156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
596 KB |
Output is correct |
3 |
Correct |
7 ms |
1748 KB |
Output is correct |
4 |
Correct |
21 ms |
4656 KB |
Output is correct |
5 |
Correct |
62 ms |
14268 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
388 KB |
Output is correct |
2 |
Correct |
2 ms |
724 KB |
Output is correct |
3 |
Correct |
7 ms |
1612 KB |
Output is correct |
4 |
Correct |
20 ms |
4560 KB |
Output is correct |
5 |
Correct |
69 ms |
14116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
6 ms |
708 KB |
Output is correct |
4 |
Correct |
2 ms |
596 KB |
Output is correct |
5 |
Correct |
6 ms |
1224 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
748 KB |
Output is correct |
3 |
Correct |
7 ms |
1684 KB |
Output is correct |
4 |
Correct |
20 ms |
4656 KB |
Output is correct |
5 |
Correct |
71 ms |
14156 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
7 ms |
1748 KB |
Output is correct |
9 |
Correct |
21 ms |
4656 KB |
Output is correct |
10 |
Correct |
62 ms |
14268 KB |
Output is correct |
11 |
Correct |
1 ms |
388 KB |
Output is correct |
12 |
Correct |
2 ms |
724 KB |
Output is correct |
13 |
Correct |
7 ms |
1612 KB |
Output is correct |
14 |
Correct |
20 ms |
4560 KB |
Output is correct |
15 |
Correct |
69 ms |
14116 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
6 ms |
708 KB |
Output is correct |
19 |
Correct |
2 ms |
596 KB |
Output is correct |
20 |
Correct |
6 ms |
1224 KB |
Output is correct |
21 |
Correct |
2 ms |
468 KB |
Output is correct |
22 |
Correct |
3 ms |
712 KB |
Output is correct |
23 |
Correct |
9 ms |
1724 KB |
Output is correct |
24 |
Correct |
23 ms |
4688 KB |
Output is correct |
25 |
Correct |
64 ms |
14268 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
748 KB |
Output is correct |
3 |
Correct |
7 ms |
1684 KB |
Output is correct |
4 |
Correct |
20 ms |
4656 KB |
Output is correct |
5 |
Correct |
71 ms |
14156 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
7 ms |
1748 KB |
Output is correct |
9 |
Correct |
21 ms |
4656 KB |
Output is correct |
10 |
Correct |
62 ms |
14268 KB |
Output is correct |
11 |
Correct |
1 ms |
388 KB |
Output is correct |
12 |
Correct |
2 ms |
724 KB |
Output is correct |
13 |
Correct |
7 ms |
1612 KB |
Output is correct |
14 |
Correct |
20 ms |
4560 KB |
Output is correct |
15 |
Correct |
69 ms |
14116 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
6 ms |
708 KB |
Output is correct |
19 |
Correct |
2 ms |
596 KB |
Output is correct |
20 |
Correct |
6 ms |
1224 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
328 KB |
Output is correct |
26 |
Correct |
2 ms |
468 KB |
Output is correct |
27 |
Correct |
3 ms |
712 KB |
Output is correct |
28 |
Correct |
9 ms |
1724 KB |
Output is correct |
29 |
Correct |
23 ms |
4688 KB |
Output is correct |
30 |
Correct |
64 ms |
14268 KB |
Output is correct |
31 |
Correct |
143 ms |
17216 KB |
Output is correct |
32 |
Correct |
64 ms |
11324 KB |
Output is correct |
33 |
Correct |
68 ms |
16208 KB |
Output is correct |
34 |
Correct |
69 ms |
10876 KB |
Output is correct |
35 |
Correct |
133 ms |
20504 KB |
Output is correct |