이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// 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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |