結果
問題 | No.2696 Sign Creation |
ユーザー |
|
提出日時 | 2024-03-22 23:25:46 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 96 ms / 2,500 ms |
コード長 | 1,599 bytes |
コンパイル時間 | 2,562 ms |
コンパイル使用メモリ | 213,324 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-20 12:33:11 |
合計ジャッジ時間 | 4,395 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include<bits/stdc++.h>using namespace std;int par[200020];int siz[200020];void init(int N) {iota(par, par + N, 0);fill(siz, siz + N, 1);}int root(int v) {return par[v] = (par[v] == v ? v : root(par[v]));}void merge(int a, int b) {a = root(a); b = root(b);if (a == b) return;if (siz[a] < siz[b]) swap(a, b);par[b] = a;siz[a] += b;}int main () {int H, W, N, D;cin >> H >> W >> N >> D;vector ST(H + 20, vector(W + 20, -1));init(N);for (int i = 0; i < N; i ++) {int a, b;cin >> a >> b;ST[a + 9][b + 9] = i;}for (int h = 10; h <= H + 10; h ++) {for (int w = 10; w <= W + 10; w ++) {if (ST[h][w] == -1) continue;int p = ST[h][w];for (int di = -D; di <= D; di ++) {int abb = D - abs(di);for (int dj = -abb; dj <= abb; dj ++) {int q = ST[h + di][w + dj];if (q != -1) {merge(p, q);}}}}}int ma = -1, mi = N + 100;int now = 0;for (int i = 0; i < N; i ++) {if (root(i) == i && siz[i] > 1) {now ++;}}for (int i = 10; i < H + 10; i ++) {for (int j = 10; j < W + 10; j ++) {if (ST[i][j] != -1) continue;unordered_set<int> st;int pq = 0;for (int di = -D; di <= D; di ++) {int abb = D - abs(di);for (int dj = -abb; dj <= abb; dj ++) {int iid = ST[i + di][j + dj];if (iid != -1) {pq ++;if (siz[root(iid)] > 1) {st.insert(root(ST[i + di][j + dj]));}}}}int sz = st.size();int nns = (pq ? now - sz + 1 : now);mi = min(mi, nns); ma = max(ma, nns);}}cout << mi << " " << ma << endl;}