//
#define _CTR_SECURE_NO_WARNINGS
#include <iostream>
#include <utility>
#include <vector>
#define x second
#define y first
typedef std::pair <int, int> pun;
typedef long long int ll;
typedef std::vector <std::vector<bool>> tabb;
typedef std::vector <std::vector<int>> tabi;
template <typename T> T in()
{
T x;
std::cin >> x;
return x;
}
enum dir
{
U, R, D, L, M
};
dir r(dir p)
{
return dir((p + 1) % M);
}
dir l(dir p)
{
return dir((p + M - 1) % M);
}
dir b(dir p)
{
return dir((p + 2) % M);
}
pun s(pun p, dir d)
{
switch (d)
{
case U: return { p.y - 1, p.x };
case R: return { p.y, p.x + 1 };
case D: return { p.y + 1, p.x };
case L: return { p.y, p.x - 1 };
default: return { -1, -1 };
}
}
tabb add;
tabi cen;
tabi wart;
int find(int);
void debug()
{
return;
std::cerr << "add:\n";
for (auto i : add)
{
for (auto j : i)std::cerr << j;
std::cerr << '\n';
}
std::cerr << "cen:\n";
for (auto i : cen)
{
for (auto j : i)std::cerr << find(j);
std::cerr << '\n';
}
}
bool dod(pun c)
{
if (add[c.y][c.x])return 0;
return add[c.y][c.x] = 1;
}
bool jes(pun c)
{
return add[c.y][c.x];
}
int tet(pun c)
{
if (c.x < 0 || c.x >= add.size() || c.y < 0 || c.y >= add[0].size())return 1;
return cen[c.y][c.x];
}
int osc(pun c)
{
return wart[c.y][c.x];
}
bool upd(pun c);
bool set(pun c, dir d)
{
if (!dod(s(c, d)) || !dod(s(c, l(d))) || !dod(s(c, r(d))))return 0;
cen[c.y][c.x] = 0;
for (dir i(U); i < M; i = dir(i + 1))
{
pun ps(s(c, i));
if (!upd(ps))return 0;
for (dir i(U); i < M; i = dir(i + 1)) if (!upd(s(ps, i)))return 0;
}
debug();
return 1;
}
bool upd(pun c)
{
if (c.x < 0 || c.x >= add.size() || c.y < 0 || c.y >= add[0].size())return 1;
if (!cen[c.y][c.x])return 1;
debug();
int jak(1);
for (dir i(U); i < M; i = dir(i + 1))if(jes(s(c, i)))jak = 10*jak + i;
if (jak == 1)return 1;
if (jak >= 10 + M)return 0;
return set(c, b(dir(jak - 10)));
}
bool end()
{
std::cout << "No\n";
return 0;
}
constexpr int maxq = 1e6 + 3;
int rep[maxq];
pun rev[maxq];
std::vector <pun> list[maxq];
int find(int w)
{
if (!rep[w])return w;
return rep[w] = find(rep[w]);
}
bool uni(int a, int b, dir d)
{
if (find(a) == find(b))return set(rev[a], d);
a = find(a);
b = find(b);
rep[a] = b;
return 1;
}
int main()
{
std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios_base::sync_with_stdio(0);
int n(in<int>()), m(in<int>());
add.resize(n + 2);
for (int i(0); i <= n + 1; ++i)add[i].resize(m + 2, !i || i > n);
for (int i(0); i <= n + 1; ++i)add[i][0] = add[i][m + 1] = 1;
cen.resize(n + 2);
for (int i(0); i <= n + 1; ++i)cen[i].resize(m + 2, 0);
wart.resize(n + 2);
for (int i(0); i <= n + 1; ++i)wart[i].resize(m + 1, 0);
for (int i(1); i <= n; ++i)for (int j(1); j <= m; ++j)std::cin >> wart[i][j];
int q(in<int>());
for (int i(1); i <= q; ++i)
{
int a(in<int>() + 1), b(in<int>() + 1);
add[a][b] = cen[a][b] = i;
rev[i] = { a, b };
}
for (int i(1); i <= n; ++i)for (int j(1); j <= m; ++j)if (!upd({ i, j })) return end();
for (int i(1); i <= n; ++i)for (int j(1); j <= m; ++j)if (cen[i][j])
{
if (cen[i - 1][j - 1] || cen[i - 1][j + 1]) { if (!set({ i, j }, D))return end(); }
else if (cen[i + 1][i + 1] || cen[i + 1][j - 1])if(!set({ i, j }, U))return end();
}
for (int i(1); i <= n; ++i)for (int j(1); j <= m; ++j)
if (cen[i][j]) for (dir d(U); d < M; d = dir(d + 1))if (tet(s(s({ i, j }, d), d)))if(!uni(cen[i][j], tet(s(s({ i, j }, d), d)), d))return end();
for (int i(1); i <= n; ++i)for (int j(1); j <= m; ++j)if (cen[i][j])list[find(cen[i][j])].push_back({ i, j });
ll odp(0);
for (int i(1); i <= q; ++i)
{
int min(1e9);
for (auto j : list[i])for (dir d(U); d < M; d = dir(d + 1))
{
add[s(j, d).y][s(j, d).x] = 1;
if (min > osc(s(j, d)))min = osc(s(j, d));
}
if(min != 1e9)odp -= min;
}
for (int i(1); i <= n; ++i)for (int j(1); j <= m; ++j)odp += ll(add[i][j])* wart[i][j];
std::cout << odp << '\n';
return 0;
}
Compilation message
covering.cpp: In function 'int tet(pun)':
covering.cpp:77:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | if (c.x < 0 || c.x >= add.size() || c.y < 0 || c.y >= add[0].size())return 1;
| ~~~~^~~~~~~~~~~~~
covering.cpp:77:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | if (c.x < 0 || c.x >= add.size() || c.y < 0 || c.y >= add[0].size())return 1;
| ~~~~^~~~~~~~~~~~~~~~
covering.cpp: In function 'bool upd(pun)':
covering.cpp:100:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | if (c.x < 0 || c.x >= add.size() || c.y < 0 || c.y >= add[0].size())return 1;
| ~~~~^~~~~~~~~~~~~
covering.cpp:100:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | if (c.x < 0 || c.x >= add.size() || c.y < 0 || c.y >= add[0].size())return 1;
| ~~~~^~~~~~~~~~~~~~~~
covering.cpp: In function 'int main()':
covering.cpp:148:31: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
148 | add[a][b] = cen[a][b] = i;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
23884 KB |
Output is correct |
| 2 |
Runtime error |
40 ms |
48640 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23884 KB |
Output is correct |
| 2 |
Runtime error |
42 ms |
48688 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
23884 KB |
Output is correct |
| 2 |
Runtime error |
40 ms |
48676 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
23804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
23756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
23884 KB |
Output is correct |
| 2 |
Runtime error |
40 ms |
48640 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
23884 KB |
Output is correct |
| 2 |
Runtime error |
40 ms |
48640 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
