結果
問題 |
No.2696 Sign Creation
|
ユーザー |
|
提出日時 | 2024-03-22 22:41:53 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 74 ms / 2,500 ms |
コード長 | 3,409 bytes |
コンパイル時間 | 10,117 ms |
コンパイル使用メモリ | 295,072 KB |
最終ジャッジ日時 | 2025-02-20 12:13:42 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2") #include <bits/stdc++.h> #define INF 1000000001LL #define LNF 1000000000000000001LL #define MOD 998244353LL #define MAX 2001 #define long long long #define all(x) x.begin(),x.end() using namespace std; //UnionFind class UnionFind { public: vector<int> parent; vector<int> cnt; void init(int size) { parent.resize(size); cnt.resize(size); for(int i = 0; i<size; i++) { parent[i] = i; cnt[i] = 1; } } int find(int x) { if(parent[x] == x) return x; return parent[x] = find(parent[x]); } void merge(int x, int y) { x = find(x); y = find(y); if(x == y) return; if(x < y) { parent[y] = x; cnt[x]+=cnt[y]; } else { parent[x] = y; cnt[y]+=cnt[x]; } } bool isUnion(int x, int y) { x = find(x); y = find(y); if(x == y) return true; return false; } }; int h,w,n,d; int trans(int x,int y) { return x*w+y; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> h >> w >> n >> d; vector<vector<bool>> pan(h,vector<bool>(w)); for(int i = 0; i<n; i++) { int a,b; cin >> a >> b; a--;b--; pan[a][b] = 1; } UnionFind uf; uf.init(h*w); for(int i = 0; i<h; i++) { for(int j = 0; j<w; j++) { if(pan[i][j] == 0) continue; for(int x = -d; x<=d; x++) { for(int y = -d; y<=d; y++) { if(i+x >= h || j+y >=w || i+x < 0 || j+y < 0 || abs(x)+abs(y) > d) continue; if(pan[i+x][j+y] == 0) continue; uf.merge(trans(i,j),trans(i+x,j+y)); } } } } int mx = -1; int mn = INF; for(int i = 0; i<h; i++) { for(int j = 0; j<w; j++) { if(pan[i][j]) continue; set<int> s; for(int x = -d; x<=d; x++) { for(int y = -d; y<=d; y++) { if(i+x >= h || j+y >=w || i+x < 0 || j+y < 0 || abs(x)+abs(y) > d) continue; if(pan[i+x][j+y] == 0) continue; s.insert(uf.find(trans(i+x,j+y))); } } int cnt = 0; bool one = false; for(int p : s) { if(uf.cnt[uf.find(p)] != 1) cnt++; one |= uf.cnt[uf.find(p)] == 1; } if(cnt > 1) cnt--; else if(cnt == 0 && one) cnt = -1; else if(cnt == 1) cnt = 0; mx = max(mx,cnt); mn = min(mn,cnt); } } int cnt = 0; for(int i = 0; i<h*w; i++) { if(uf.find(i) == i && pan[i/w][i%w] && uf.cnt[i] != 1) cnt++; } cout << cnt-mx << " " << cnt-mn << endl; return 0; }