結果
問題 | No.2696 Sign Creation |
ユーザー |
|
提出日時 | 2024-03-28 16:20:36 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,577 bytes |
コンパイル時間 | 7,305 ms |
コンパイル使用メモリ | 325,780 KB |
実行使用メモリ | 93,752 KB |
最終ジャッジ日時 | 2024-12-20 12:52:50 |
合計ジャッジ時間 | 18,705 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 TLE * 1 WA * 19 |
ソースコード
#include<bits/stdc++.h>using namespace std;#include<atcoder/all>using namespace atcoder;#define rep(i,n) for (int i = 0; i < (n); ++i)using ld = long double;using ll = long long;template<class T> bool chmax(T &a, T b){if(a<b){a = b;return true;}return false;}template<class T> bool chmin(T &a, T b){if(a>b){a = b;return true;}return false;}struct RollbackUnionFind {vector<int> data;stack<pair<int, int> > history;int inner_snap;RollbackUnionFind(int sz) : inner_snap(0) { data.assign(sz, -1); }bool unite(int x, int y) {x = find(x), y = find(y);history.emplace(x, data[x]);history.emplace(y, data[y]);if (x == y) return false;if (data[x] > data[y]) swap(x, y);data[x] += data[y];data[y] = x;return true;}int find(int k) {if (data[k] < 0) return k;return find(data[k]);}int same(int x, int y) { return find(x) == find(y); }int size(int k) { return (-data[find(k)]); }void undo() {data[history.top().first] = history.top().second;history.pop();data[history.top().first] = history.top().second;history.pop();}void snapshot() { inner_snap = int(history.size() >> 1); }int get_state() { return int(history.size() >> 1); }void rollback(int state = -1) {if (state == -1) state = inner_snap;state <<= 1;assert(state <= (int)history.size());while (state < (int)history.size()) undo();}};using P = pair<int,int>;int H, W, N, D, X[1<<18], Y[1<<18], A[1<<18], B[1<<18];int main(){cin >> H >> W >> N >> D;rep(i,N) cin >> X[i] >> Y[i];map<P,int> mp;rep(i,N){A[i] = X[i]-Y[i];B[i] = X[i]+Y[i];mp[make_pair(A[i], B[i])] = i;}RollbackUnionFind d(N+1);set<int> st;rep(i,N){for(int x = A[i]-D; x<=A[i]+D; x++) for(int y = B[i]-D; y<=B[i]+D; y++){P key = make_pair(x,y);auto it = mp.find(key);if(it==mp.end()||mp[key]==i) continue;d.unite(i,mp[key]);st.insert(i);}}d.snapshot();set<int> st2;for(auto n : st) st2.insert(d.find(n));int mx = st2.size();if(mx==0){cout << "0 1" << endl;return 0;}int mn = N;rep(i,H) rep(j,W){P key = make_pair(i-j,i+j);auto it = mp.find(key);if(it!=mp.end()) continue;set<int> st3;for(int x = i-j-D; x<=i-j+D; x++) for(int y = i+j-D; y<=i+j+D; y++){P key2 = make_pair(x,y);auto it = mp.find(key2);if(it==mp.end()||!st.count(mp[key2])) continue;st3.insert(d.find(mp[key2]));}chmin(mn, mx+1-(int)st3.size());}cout << mn << " " << mx << endl;}