結果
問題 | No.2696 Sign Creation |
ユーザー |
![]() |
提出日時 | 2024-03-22 22:05:09 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 80 ms / 2,500 ms |
コード長 | 2,819 bytes |
コンパイル時間 | 3,864 ms |
コンパイル使用メモリ | 281,384 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-20 11:57:42 |
合計ジャッジ時間 | 5,255 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include<bits/stdc++.h>namespace {#pragma GCC diagnostic ignored "-Wunused-function"#include<atcoder/all>#pragma GCC diagnostic warning "-Wunused-function"using namespace std;using namespace atcoder;#define rep(i,n) for(int i = 0; i < (int)(n); i++)#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)#define all(x) begin(x), end(x)#define rall(x) rbegin(x), rend(x)template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }using ll = long long;using P = pair<int,int>;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;template<int element_size>struct array_set {int state[element_size]; // -1 if not in set else index in elemsint elems[element_size];int size = 0;array_set() { memset(state, -1, sizeof(int) * element_size); }void insert(int x) {if (state[x] == -1) {state[x] = size;elems[size] = x;size++;}}bool contains(int x) { return state[x] != -1; }int* begin() { return elems; }int* end() { return elems + size; }void clear() { while(size) state[elems[--size]] = -1; }void erase(int x) { // not testedint idx = state[x];if (idx != -1) {state[x] = -1;size--;if (idx != size) {int y = elems[size];state[y] = idx;elems[idx] = y;}}}};} int main() {ios::sync_with_stdio(false);cin.tie(0);int h, w, n, d;cin >> h >> w >> n >> d;vector<P> didj;for (int i = -d; i <= d; i++) {for (int j = -d; j <= d; j++) {if (i == 0 && j == 0) continue;if (abs(i) + abs(j) <= d) didj.emplace_back(i, j);}}VVI id(h, VI(w, -1));rep(i, n) {int x, y;cin >> x >> y;x--, y--;id[x][y] = i;}dsu uf(n);auto idxchk = [&](int i, int j) { return 0 <= i && i < h && 0 <= j && j < w; };rep(i, h) rep(j, w) if (id[i][j] != -1) {for (auto [di, dj] : didj) {int ni = i + di, nj = j + dj;if (!idxchk(ni, nj)) continue;if (id[ni][nj] != -1) uf.merge(id[i][j], id[ni][nj]);}}int now = 0;rep(i, n) now += uf.leader(i) == i && uf.size(i) >= 2;int mn = h * w + 1, mx = -1;rep(i, h) rep(j, w) if (id[i][j] == -1) {static array_set<100010> st;st.clear();for (auto [di, dj] : didj) {int ni = i + di, nj = j + dj;if (!idxchk(ni, nj) || id[ni][nj] == -1) continue;st.insert(uf.leader(id[ni][nj]));}int cnt = now;int new_size = 1;for (int i : st) {cnt -= uf.size(i) >= 2;new_size += uf.size(i);}cnt += new_size >= 2;chmin(mn, cnt);chmax(mx, cnt);}cout << mn << ' ' << mx << '\n';}