이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int, int>
#define fi first
#define se second
const int N = 1e6 + 3;
int n, m, k, t, x, y, u, v;
ll ans = 0;
pi p[N];
vector<int> adj[N];
queue<pi> q;
priority_queue<int, vector<int>, greater<int> > pq;
int tx[4] = {0, 1, 0, -1}, ty[4] = {1, 0, -1, 0};
bool check (int u, int v) {
return (0 <= u && u < n && 0 <= v && v < m);
}
pi toado (int k) {
int x = k / m;
int y = k % m;
return {x, y};
}
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
vector<vector<int> > a(n + 1), d(n + 1);
vector<vector<bool> > c(n + 1), vis(n + 1);
for (int i = 0; i < n; ++ i) {
a[i].resize(m + 1);
d[i].resize(m + 1, 0);
c[i].resize(m + 1, 0);
vis[i].resize(m + 1, 0);
for (int j = 0; j < m; ++ j) cin >> a[i][j];
}
// pi banh = toado(5);
// cout << banh.fi << ' ' << banh.se << '\n';
cin >> k;
t = k;
for (int i = 1; i <= k; ++ i) {
cin >> p[i].fi >> p[i].se;
tie(x, y) = p[i];
c[x][y] = 1;
d[x][y] ++;
ans += a[x][y];
int cnt = 0;
for (int j = 0; j < 4; ++ j) {
u = x + tx[j], v = y + ty[j];
if (check(u, v))
cnt ++,
d[u][v] ++,
ans += a[u][v],
adj[x * m + y].push_back(u * m + v),
adj[u * m + v].push_back(x * m + y);
}
if (cnt < 3) return cout << "No", 0;
}
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < m; ++ j) {
if (c[i][j] && !vis[i][j]) {
vis[i][j] = 1;
q.push({i, j});
int S = 0, SN = 0, SD = 0;
while (!q.empty()) {
tie(x, y) = q.front();
int t = d[x][y] - 1;
ans -= (t * a[x][y]);
S -= t;
if (!c[x][y]) pq.push(a[x][y]), SD ++;
else S ++, SN ++;
q.pop();
for (int z : adj[x * m + y]) {
pi banh = toado(z);
tie(u, v) = banh;
if (!vis[u][v]) {
vis[u][v] = 1;
q.push({u, v});
}
}
}
// cout << SN << ' ' << SD << ' ' << S << '\n';
while (!pq.empty()) {
if (S > 0) S --, ans -= pq.top(), SD --;
pq.pop();
}
if (SD != 3 * SN) return cout << "No", 0;
}
}
}
cout << ans;
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... |