結果
問題 | No.2696 Sign Creation |
ユーザー |
|
提出日時 | 2024-03-22 22:41:53 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 90 ms / 2,500 ms |
コード長 | 3,409 bytes |
コンパイル時間 | 3,753 ms |
コンパイル使用メモリ | 239,236 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-20 12:13:31 |
合計ジャッジ時間 | 5,741 ms |
ジャッジサーバーID (参考情報) |
judge5 / 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;//UnionFindclass 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;}