Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Forget needy cells for a minute. Color every cell by . If you delete one color class, pigeonhole says the remaining two classes have at least of the total non-needy value. Now ask: is that remaining graph drawable legally?
The operation is secretly a graph condition. A set of cells can be colored in some order iff the graph induced by those cells is a forest. Cycles are death: the last vertex of a cycle would have two already-black neighbors.
For a fixed residue , the graph using only cells with is a forest. Look at diagonals : after removing one residue, edges only live between pairs of consecutive diagonals, and each such strip is just a path.
Needy cells of the deleted residue must be forced back in. This can create cycles. Whenever a forced needy cell lies on a cycle, delete some ordinary . cell from that cycle. This preserves all needy cells and all special cells. The “no special next to needy” condition is exactly there so such a deletable . exists.
Try all three residues. For residue , if needy cells are forced back, the cycle rank can increase by at most because each added grid vertex has degree at most . So we delete at most ordinary cells. Summing values over the three residues gives at least , hence one construction has value at least . Pick that one and output a DFS preorder of its forest.
Reference used for cross-checking: official Codeforces Round 1085 editorial/implementation.
Take any final set of black cells and build the graph where cells are vertices and side-adjacent black cells are edges.
A set is colorable exactly when this graph is a forest.
Why? If the graph has a cycle, look at the last vertex of that cycle colored black. Its two cycle-neighbors were already black, so the move was illegal. Conversely, if the graph is a forest, root every tree and output a DFS preorder. Every non-root vertex has only its parent already black when it is colored. Nice and clean.
So the real task is: construct a high-value forest containing every needy cell.
Color cell by
First suppose there are no needy cells. If we delete all non-needy cells of one residue , the remaining value is , where is the total value of non-needy cells with color . Since
some residue has , so keeping the other two residues gives value at least .
The important structural fact: the cells with colors different from induce a forest.
Look at diagonals . Edges only go between diagonals whose sums differ by . After removing all cells with , the remaining graph splits into independent strips between two consecutive diagonals:
The adjacency graph between two consecutive grid diagonals is just a path. Therefore the whole thing is a forest. No cycle, no bullshit.
Now needy cells exist, and every needy cell must be kept.
For a residue , start with all cells except non-needy cells of color . Equivalently:
The base graph without those forced-back needy cells is a forest. Adding needy cells of color may create cycles. We repair this greedily:
For every needy cell of color , while lies on a cycle, find such a cycle and delete one . cell from it.
This never deletes a needy cell. It also never deletes a special cell: any cycle containing a needy cell must contain some non-needy cell, otherwise the required needy cells themselves would contain a cycle, contradicting the guarantee that all needy cells can be shaded. Along the cycle, when we first leave needy cells, the next non-needy cell borders a needy cell, so it cannot be special. Thus it is ..
After processing a needy cell, deleting vertices later cannot create new cycles through it. Once all forced cells are processed, no cycle remains, because every cycle would need at least one forced-back color- needy cell. So we get a forest containing all needy cells.
Let:
. cells deleted during repair for residue ;For residue , the final value is
The term is the non-needy value we kept initially. All needy cells contribute . Every deleted ordinary cell costs .
Now bound . The initial graph before forcing color- needy cells is a forest, so its cycle rank is . Adding one needy cell adds at most edges, hence increases the cycle rank by at most . Therefore after adding such cells, the cycle rank is at most
Every deletion is made from an actual cycle, so it decreases the cycle rank by at least . Hence
Summing over :
Using :
So at least one residue satisfies
Try all three and keep the best. That is the whole trick.
The selected cells form a forest. Run DFS over this forest and output vertices in preorder. A vertex is colored before its children, so it has at most one already-black neighbor: its parent.
For each residue and each repair step, we run a DFS over at most cells. The number of repair steps is , so one test case costs
The statement guarantees
so this is easily fast enough. Memory is
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int DR[4] = {-1, 0, 1, 0};
const int DC[4] = {0, -1, 0, 1};
struct Candidate {
ll value = 0;
vector<vector<char>> take;
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, m;
ll a, b;
cin >> n >> m >> a >> b;
vector<string> g(n);
for (auto &row : g) cin >> row;
auto id = [&](int r, int c) {
return r * m + c;
};
auto inside = [&](int r, int c) {
return 0 <= r && r < n && 0 <= c && c < m;
};
auto build = [&](int banned) -> Candidate {
Candidate res;
res.take.assign(n, vector<char>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
res.take[i][j] = ((i + j) % 3 != banned || g[i][j] == '#');
}
}
for (int sr = 0; sr < n; sr++) {
for (int sc = 0; sc < m; sc++) {
if ((sr + sc) % 3 != banned || g[sr][sc] != '#') continue;
int root = id(sr, sc);
while (true) {
vector<int> parent(n * m, -1);
function<void(int, int)> dfs = [&](int v, int p) {
int r = v / m, c = v % m;
for (int dir = 0; dir < 4; dir++) {
int nr = r + DR[dir], nc = c + DC[dir];
if (!inside(nr, nc) || !res.take[nr][nc]) continue;
int to = id(nr, nc);
if (to == p || parent[to] != -1) continue;
parent[to] = v;
dfs(to, v);
}
};
dfs(root, -1);
if (parent[root] == -1) break;
int cur = root;
while (g[cur / m][cur % m] != '.') {
cur = parent[cur];
}
res.take[cur / m][cur % m] = 0;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (res.take[i][j]) {
res.value += (g[i][j] == 'x' ? b : a);
}
}
}
return res;
};
Candidate best = build(0);
for (int banned = 1; banned < 3; banned++) {
Candidate cur = build(banned);
if (cur.value > best.value) best = move(cur);
}
vector<vector<char>> vis(n, vector<char>(m, 0));
vector<pair<int, int>> ans;
function<void(int, int)> out_dfs = [&](int r, int c) {
vis[r][c] = 1;
ans.push_back({r + 1, c + 1});
for (int dir = 0; dir < 4; dir++) {
int nr = r + DR[dir], nc = c + DC[dir];
if (!inside(nr, nc)) continue;
if (vis[nr][nc] || !best.take[nr][nc]) continue;
out_dfs(nr, nc);
}
};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (best.take[i][j] && !vis[i][j]) {
out_dfs(i, j);
}
}
}
cout << ans.size() << '\n';
for (auto [r, c] : ans) {
cout << r << ' ' << c << '\n';
}
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int DR[4] = {-1, 0, 1, 0};
const int DC[4] = {0, -1, 0, 1};
struct Candidate {
ll value = 0;
vector<vector<char>> take;
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, m;
ll a, b;
cin >> n >> m >> a >> b;
vector<string> g(n);
for (auto &row : g) cin >> row;
auto id = [&](int r, int c) {
return r * m + c;
};
auto inside = [&](int r, int c) {
return 0 <= r && r < n && 0 <= c && c < m;
};
auto build = [&](int banned) -> Candidate {
Candidate res;
res.take.assign(n, vector<char>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
res.take[i][j] = ((i + j) % 3 != banned || g[i][j] == '#');
}
}
for (int sr = 0; sr < n; sr++) {
for (int sc = 0; sc < m; sc++) {
if ((sr + sc) % 3 != banned || g[sr][sc] != '#') continue;
int root = id(sr, sc);
while (true) {
vector<int> parent(n * m, -1);
function<void(int, int)> dfs = [&](int v, int p) {
int r = v / m, c = v % m;
for (int dir = 0; dir < 4; dir++) {
int nr = r + DR[dir], nc = c + DC[dir];
if (!inside(nr, nc) || !res.take[nr][nc]) continue;
int to = id(nr, nc);
if (to == p || parent[to] != -1) continue;
parent[to] = v;
dfs(to, v);
}
};
dfs(root, -1);
if (parent[root] == -1) break;
int cur = root;
while (g[cur / m][cur % m] != '.') {
cur = parent[cur];
}
res.take[cur / m][cur % m] = 0;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (res.take[i][j]) {
res.value += (g[i][j] == 'x' ? b : a);
}
}
}
return res;
};
Candidate best = build(0);
for (int banned = 1; banned < 3; banned++) {
Candidate cur = build(banned);
if (cur.value > best.value) best = move(cur);
}
vector<vector<char>> vis(n, vector<char>(m, 0));
vector<pair<int, int>> ans;
function<void(int, int)> out_dfs = [&](int r, int c) {
vis[r][c] = 1;
ans.push_back({r + 1, c + 1});
for (int dir = 0; dir < 4; dir++) {
int nr = r + DR[dir], nc = c + DC[dir];
if (!inside(nr, nc)) continue;
if (vis[nr][nc] || !best.take[nr][nc]) continue;
out_dfs(nr, nc);
}
};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (best.take[i][j] && !vis[i][j]) {
out_dfs(i, j);
}
}
}
cout << ans.size() << '\n';
for (auto [r, c] : ans) {
cout << r << ' ' << c << '\n';
}
}
return 0;
}