結果
問題 | No.2696 Sign Creation |
ユーザー |
![]() |
提出日時 | 2024-03-22 22:55:34 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,364 bytes |
コンパイル時間 | 2,668 ms |
コンパイル使用メモリ | 217,088 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-20 12:20:18 |
合計ジャッジ時間 | 4,564 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 WA * 1 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define all(v) (v).begin(),(v).end()#define pb(a) push_back(a)#define rep(i, n) for(int i=0;i<n;i++)#define foa(e, v) for(auto&& e : v)using ll = long long;const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60);#define dout(a) cout<<fixed<<setprecision(10)<<a<<endl;struct UnionFind {vector<int> par;UnionFind(int n) :par(n, -1) { }void init(int n) { par.assign(n, -1); }int root(int x) {if (par[x] < 0) return x;else return par[x] = root(par[x]);}bool connect(int x, int y) {x = root(x); y = root(y);if (x == y) return false;if (par[x] > par[y]) swap(x, y);par[x] += par[y];par[y] = x;return true;}int size(int x) {return -par[root(x)];}};int main() {cin.tie(0);ios::sync_with_stdio(false);int h, w, n, d;cin >> h >> w >> n >> d;vector<int> x(n), y(n);UnionFind uf(n);vector<vector<int>> id(h, vector<int> (w, -1));rep(i, n) {cin >> x[i] >> y[i];x[i] --;y[i] --;id[x[i]][y[i]] = i;}vector<int> dx, dy;for(int i = -d; i <= d; i ++) for(int j = -d; j <= d; j ++) {if(abs(i) + abs(j) <= d) {dx.pb(i);dy.pb(j);}}int sz = dx.size();rep(idx, n) {rep(k, sz) {int i = x[idx] + dx[k];int j = y[idx] + dy[k];if(i < 0 or i >= h or j < 0 or j >= w) continue;if(id[i][j] != -1) uf.connect(id[i][j], idx);}}set<int> st;rep(i, n) if(uf.size(i) != 1) st.insert(uf.root(i));int Min = st.size(), Max = st.size();int base = st.size();rep(X, h) rep(Y, w) {set<int> st1, st2;rep(k, sz) {int i = X + dx[k];int j = Y + dy[k];if(i < 0 or i >= h or j < 0 or j >= w) continue;if(id[i][j] != -1) {if(uf.size(id[i][j]) == 1) st1.insert(uf.root(id[i][j]));else st2.insert(uf.root(id[i][j]));}}if(!st2.empty()) {Min = min(Min, base - (int)(st2.size() - 1));} else if(!st1.empty()) {Max = max(Max, base + 1);}}cout << Min << " " << Max << endl;return 0;}