結果

問題 No.2696 Sign Creation
ユーザー KowerKoint2010KowerKoint2010
提出日時 2024-02-13 15:56:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 10,002 bytes
コンパイル時間 2,983 ms
コンパイル使用メモリ 227,448 KB
最終ジャッジ日時 2025-02-19 05:54:53
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 37 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#line 2 "/home/kowerkoint/workspace/CompPro-Make/library/KowerKoint/stl-expansion.hpp"
#include <bits/stdc++.h>
template <typename T1, typename T2>
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p) {
is >> p.first >> p.second;
return is;
}
template <typename T, size_t N>
std::istream& operator>>(std::istream& is, std::array<T, N>& a) {
for (size_t i = 0; i < N; ++i) {
is >> a[i];
}
return is;
}
template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
for (auto& e : v) is >> e;
return is;
}
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
os << p.first << " " << p.second;
return os;
}
template <typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
for (size_t i = 0; i < N; ++i) {
os << a[i] << (i + 1 == a.size() ? "" : " ");
}
return os;
}
template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
for (size_t i = 0; i < v.size(); ++i) {
os << v[i] << (i + 1 == v.size() ? "" : " ");
}
return os;
}
#line 3 "/home/kowerkoint/workspace/CompPro-Make/library/KowerKoint/base.hpp"
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for(ll i = a; i < (ll)(b); i++)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define END(...) { print(__VA_ARGS__); return; }
using VI = vector<int>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
using ll = long long;
using VL = vector<ll>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;
using ull = unsigned long long;
using VUL = vector<ull>;
using VVUL = vector<VUL>;
using VVVUL = vector<VVUL>;
using VD = vector<double>;
using VVD = vector<VD>;
using VVVD = vector<VVD>;
using VS = vector<string>;
using VVS = vector<VS>;
using VVVS = vector<VVS>;
using VC = vector<char>;
using VVC = vector<VC>;
using VVVC = vector<VVC>;
using P = pair<int, int>;
using VP = vector<P>;
using VVP = vector<VP>;
using VVVP = vector<VVP>;
using LP = pair<ll, ll>;
using VLP = vector<LP>;
using VVLP = vector<VLP>;
using VVVLP = vector<VVLP>;
template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using GPQ = priority_queue<T, vector<T>, greater<T>>;
constexpr int INF = 1001001001;
constexpr ll LINF = 1001001001001001001ll;
constexpr int DX[] = {1, 0, -1, 0};
constexpr int DY[] = {0, 1, 0, -1};
void print() { cout << '\n'; }
template<typename T>
void print(const T &t) { cout << t << '\n'; }
template<typename Head, typename... Tail>
void print(const Head &head, const Tail &... tail) {
cout << head << ' ';
print(tail...);
}
#ifdef DEBUG
void dbg() { cerr << '\n'; }
template<typename T>
void dbg(const T &t) { cerr << t << '\n'; }
template<typename Head, typename... Tail>
void dbg(const Head &head, const Tail &... tail) {
cerr << head << ' ';
dbg(tail...);
}
#else
template<typename... Args>
void dbg(const Args &... args) {}
#endif
template<typename T>
vector<vector<T>> split(typename vector<T>::const_iterator begin, typename vector<T>::const_iterator end, T val) {
vector<vector<T>> res;
vector<T> cur;
for(auto it = begin; it != end; it++) {
if(*it == val) {
res.push_back(cur);
cur.clear();
} else cur.push_back(*it);
}
res.push_back(cur);
return res;
}
vector<string> split(typename string::const_iterator begin, typename string::const_iterator end, char val) {
vector<string> res;
string cur = "";
for(auto it = begin; it != end; it++) {
if(*it == val) {
res.push_back(cur);
cur.clear();
} else cur.push_back(*it);
}
res.push_back(cur);
return res;
}
template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template <typename T>
pair<VI, vector<T>> compress(const vector<T> &a) {
int n = a.size();
vector<T> x;
REP(i, n) x.push_back(a[i]);
sort(ALL(x)); x.erase(unique(ALL(x)), x.end());
VI res(n);
REP(i, n) res[i] = lower_bound(ALL(x), a[i]) - x.begin();
return make_pair(res, x);
}
template <typename It>
auto rle(It begin, It end) {
vector<pair<typename It::value_type, int>> res;
if(begin == end) return res;
auto pre = *begin;
int num = 1;
for(auto it = begin + 1; it != end; it++) {
if(pre != *it) {
res.emplace_back(pre, num);
pre = *it;
num = 1;
} else num++;
}
res.emplace_back(pre, num);
return res;
}
template <typename It>
vector<pair<typename It::value_type, int>> rle_sort(It begin, It end) {
vector<typename It::value_type> cloned(begin, end);
sort(ALL(cloned));
auto e = rle(ALL(cloned));
sort(ALL(e), [](const auto& l, const auto& r) { return l.second < r.second; });
return e;
}
template <typename T>
pair<vector<T>, vector<T>> factorial(int n) {
vector<T> res(n+1), rev(n+1);
res[0] = 1;
REP(i, n) res[i+1] = res[i] * (i+1);
rev[n] = 1 / res[n];
for(int i = n; i > 0; i--) {
rev[i-1] = rev[i] * i;
}
return make_pair(res, rev);
}
#line 2 "/home/kowerkoint/workspace/CompPro-Make/library/rainbou/cpp/unionfind.hpp"
/**
* @file unionfind.hpp
* @brief UnionFind
*/
#line 11 "/home/kowerkoint/workspace/CompPro-Make/library/rainbou/cpp/unionfind.hpp"
/**
* @brief 2
*/
struct UnionFind {
private:
int _n;
//
std::vector<int> parent_or_size;
public:
UnionFind() : _n(0) {}
explicit UnionFind(int n) : _n(n), parent_or_size(n, -1) {}
/**
* @brief (a,b)
* @return
*/
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
/**
* @brief a,b
*/
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
/**
* @brief a
*/
int leader(int a) {
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0) return a;
int x = a;
while (parent_or_size[x] >= 0) {
x = parent_or_size[x];
}
while (parent_or_size[a] >= 0) {
int t = parent_or_size[a];
parent_or_size[a] = x;
a = t;
}
return x;
}
/**
* @brief a
*/
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
/**
* @brief
* @return
*/
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
};
#line 3 "main.cpp"
void solve(){
ll h, w, n, d; cin >> h >> w >> n >> d;
VLP xy(n); cin >> xy;
map<LP, int> mp; REP(i, n) mp[xy[i]] = i;
UnionFind uf(n);
REP(i, n) {
auto [x, y] = xy[i];
for(int dx = -d; dx <= d; dx++) {
for(int dy = abs(dx)-d; dy <= d-abs(dx); dy++) {
ll nx = x+dx, ny = y+dy;
if(nx < 1 || ny < 1 || nx > h || ny > w) continue;
if(auto it = mp.find({nx, ny}); it != mp.end()) uf.merge(i, it->second);
}
}
}
auto groups = uf.groups();
int m = groups.size();
VI isolate(n);
map<LP, pair<int, int>> near_groups;
REP(i, m) {
const auto &v = groups[i];
if(v.size() == 1) isolate[v[0]] = 1;
VLP near;
for(int j : v) {
auto [x, y] = xy[j];
for(int dx = -d; dx <= d; dx++) {
for(int dy = abs(dx)-d; dy <= d-abs(dx); dy++) {
ll nx = x+dx, ny = y+dy;
if(nx < 1 || ny < 1 || nx > h || ny > w) continue;
near.emplace_back(nx, ny);
}
}
}
sort(ALL(near));
near.erase(unique(ALL(near)), near.end());
for(const auto &[x, y] : near) {
near_groups[{x, y}].first++;
if(v.size() == 1) near_groups[{x, y}].second++;
}
}
int isolates = accumulate(ALL(isolate), 0);
ll mx = 0, mn = INF;
for(const auto &[ng, ni] : near_groups) {
chmax(mx, (m+1-ni.first) - (isolates-ni.second));
chmin(mn, (m+1-ni.first) - (isolates-ni.second));
}
if((ll)near_groups.size() < h*w) {
chmax(mx, m+1-isolates-1);
chmin(mn, m+1-isolates-1);
}
print(mn, mx);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(10);
int t = 1;
// cin >> t;
for(int case_id = 1; case_id <= t; case_id++) solve();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0