이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int Limit = 1e6;
const int LimitVal = 1000;
const int dirx[4] = {-1, 0, 1, 0};
const int diry[4] = {0, 1, 0, -1};
const int Cornerdirx[4] = {-1, 1, 1, -1};
const int Cornerdiry[4] = {1, 1, -1, -1};
int m, n, k;
vector<vector<int>> Grid, Status;
vector<int> Dsu;
bool InGrid(int& i, int& j) {
return (0 <= i && i < m && 0 <= j && j < n);
}
int Zip(int& i, int& j) {
return i * n + j;
}
int FindPar(int u) {
if (u == Dsu[u]) return u;
return Dsu[u] = FindPar(Dsu[u]);
}
bool Union(int u , int v) {
u = FindPar(u);
v = FindPar(v);
if (u == v) return false;
Dsu[v] = u;
return true;
}
vector<pair<int, int>> Component[Limit];
vector<vector<bool>> isVisited;
vector<pair<int, int>> isVisited_RollBack;
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> m >> n;
Grid.resize(m + 1, vector<int>(n + 1));
Status.resize(m + 1, vector<int>(n + 1));
Dsu.resize(n * m + 1);
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> Grid[i][j], Dsu[Zip(i, j)] = Zip(i, j);
cin >> k;
for (int i = 1; i <= k; i++) {
int x, y;
cin >> x >> y;
Status[x][y] = true;
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (Status[i][j] == false) continue;
for (int dir = 0; dir < 4; dir++) {
pair<int, int> CloseAdj = {i + dirx[dir], j + diry[dir]};
pair<int, int> FarAdj = {i + 2 * dirx[dir], j + 2 * diry[dir]};
pair<int, int> CornerAdj = {i + Cornerdirx[dir], j + Cornerdiry[dir]};
if (InGrid(CloseAdj.first, CloseAdj.second) && Status[CloseAdj.first][CloseAdj.second] == true)
Union(Zip(i, j), Zip(CloseAdj.first, CloseAdj.second));
if (InGrid(FarAdj.first, FarAdj.second) && Status[FarAdj.first][FarAdj.second] == true)
Union(Zip(i, j), Zip(FarAdj.first, FarAdj.second));
if (InGrid(CornerAdj.first, CornerAdj.second) && Status[CornerAdj.first][CornerAdj.second] == true)
Union(Zip(i, j), Zip(CornerAdj.first, CornerAdj.second));
}
}
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (Status[i][j] == true)
Component[FindPar(Zip(i, j))].emplace_back(i, j);
int Ans = 0;
isVisited.resize(m + 1, vector<bool>(n + 1));
for (int i = 0; i < n * m; i++) {
if (Component[i].empty()) continue;
int CoverNum = 0, MaxSum = 0;
for (auto& c: Component[i]) {
MaxSum += Grid[c.first][c.second];
for (int dir = 0; dir < 4; dir++) {
int Cx = c.first + dirx[dir];
int Cy = c.second + diry[dir];
if (!InGrid(Cx, Cy) || Status[Cx][Cy] == true) continue;
if (!isVisited[Cx][Cy]) {
isVisited[Cx][Cy] = true;
isVisited_RollBack.emplace_back(Cx, Cy);
CoverNum++;
}
}
}
if (CoverNum < 3 * (int)Component[i].size()) {
cout << "No";
return 0;
} else if (CoverNum == 3 * (int)Component[i].size()) {
for (auto& c: isVisited_RollBack)
MaxSum += Grid[c.first][c.second];
} else {
int MinVal = LimitVal;
for (auto& c: isVisited_RollBack) {
MaxSum += Grid[c.first][c.second];
MinVal = min(MinVal, Grid[c.first][c.second]);
}
MaxSum -= MinVal;
}
Ans += MaxSum;
for (auto& c: isVisited_RollBack)
isVisited[c.first][c.second] = 0;
isVisited_RollBack.clear();
}
cout << Ans;
}
# | 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... |