Codeforces Round #500 (Div. 1) [based on EJOI]: B. Chemical table
problem
$H \times W \le (2 \cdot 10^5) \times (2 \cdot 10^5)$ の盤面があり$q \le 2 \cdot 10^5$マスが黒く塗られ残りは白い。 次の操作を好きな回数行なってマスをすべて黒にしたい: (軸平行な)長方形をなすよう$4$マス選んでそのうち$3$マスが黒く塗られているとき、残りの$1$マスも黒く塗れる。 しかしこの操作だけだとすべて黒にはできないかもしれないので、最初に好きな数のマスを黒にすることができる。 その黒にするマスの個数の最小値を答えよ。
solution
行と列に対応する頂点を作って二部グラフ (典型)。 操作は連結成分の内部を密にしてその部分を完全二部グラフにできると主張しているので、単に連結成分の個数$k$を数えて$k - 1$。 $O(HW)$。
ただ図を書いて試しているとだけでも分かる。 例えば次のような状況から:
................................
...#............................
................................
...#..........#.................
................................
...........................#....
................................
..............#............#....
このように塗れる:
................................
...#..........#............#....
................................
...#..........#............#....
................................
...#..........#............#....
................................
...#..........#............#....
行や列の交換はしても変わらないので次のように見れる:
###.............................
###.............................
###.............................
###.............................
................................
................................
................................
................................
連結成分が複数なら次のように:
###.............................
###.............................
###.............................
###.............................
...################.............
...################.............
...................#............
................................
この形を作って、さらにひとつに繋ぐのに必要なマスを数えればよい。
note
行と列に対応する頂点を作るのは典型なので気付いてはいたが、単にマスの塗り方の話だけで考えていたら解けた。 もちろんグラフは書いていたがマスとマスの間に直接に辺を貼るもの。 連結成分という形での整理は後から。 両方で解けるの不思議だなあという気もするが明らかな気もする。
implementation
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define ALL(x) begin(x), end(x)
using namespace std;
int main() {
// input
int h, w, q; scanf("%d%d%d", &h, &w, &q);
vector<vector<int> > row(h), col(w);
REP (i, q) {
int y, x; scanf("%d%d", &y, &x);
-- y; -- x;
row[y].push_back(x);
col[x].push_back(y);
}
// solve
vector<bool> row_used(h), col_used(w);
function<void (int)> go_row, go_col;
go_row = [&](int y) {
assert (not row_used[y]);
row_used[y] = true;
for (int x : row[y]) if (not col_used[x]) {
go_col(x);
}
};
go_col = [&](int x) {
assert (not col_used[x]);
col_used[x] = true;
for (int y : col[x]) if (not row_used[y]) {
go_row(y);
}
};
int block_count = 0;
REP (y, h) if (not row_used[y]) {
++ block_count;
go_row(y);
}
int row_unused = count(ALL(row_used), false);
int col_unused = count(ALL(col_used), false);
int answer = block_count - 1 + row_unused + col_unused;
// output
cout << answer << endl;
return 0;
}