結果

問題 No.2696 Sign Creation
コンテスト
ユーザー Nachia
提出日時 2024-03-22 22:59:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 85 ms / 2,500 ms
コード長 3,802 bytes
コンパイル時間 1,627 ms
コンパイル使用メモリ 117,108 KB
最終ジャッジ日時 2025-02-20 12:23:21
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <array>
#include <cmath>
#include <atcoder/modint>
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(i64 i=0; i<(i64)(n); i++)
#define repr(i,n) for(i64 i=(i64)(n)-1; i>=0; i--)
const i64 INF = 1001001001001001001;
const char* yn(bool x){ return x ? "Yes" : "No"; }
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
template<typename A> using nega_queue = std::priority_queue<A,std::vector<A>,std::greater<A>>;
using Modint = atcoder::static_modint<998244353>;
//#include "nachia/vec.hpp"
#include <atcoder/dsu>
using namespace std;

void testcase(){
    i64 H, W, N; cin >> H >> W >> N;
    i64 D; cin >> D;

    vector<pair<i64,i64>> P(N);
    for(auto& [x,y] : P){ cin >> x >> y; x--; y--; }
    sort(P.begin(), P.end());

    auto dist = [&](i64 a, i64 b) -> i64 {
        return abs(P[a].first - P[b].first) + abs(P[a].second - P[b].second);
    };

    vector<i64> iso(N);
    atcoder::dsu dsu(N);

    vector<vector<int>> star(H, vector<int>(W, -1));
    rep(i,N) star[P[i].first][P[i].second] = i;
    rep(x,H) rep(y,W) if(star[x][y] >= 0) for(int dx=-D; dx<=D; dx++){
        int d = D - abs(dx);
        for(int dy=-d; dy<=d; dy++) if(0 <= x+dx && x+dx < H && 0 <= y+dy && y+dy < W){
            if(star[x+dx][y+dy] >= 0){
                dsu.merge(star[x][y], star[x+dx][y+dy]);
            }
        }
    }

    rep(i,N) iso[i] = (dsu.size(i) == 1 ? 1 : 0);

    vector<int> C(N, -1);
    int ci = -1;
    int maxmerge = 0;
    int minmerge = 1001001001;
    rep(x,H) rep(y,W) if(star[x][y] == -1){
        int count = 0;
        ci++;
        for(int dx=-D; dx<=D; dx++){
            int d = D - abs(dx);
            for(int dy=-d; dy<=d; dy++) if(0 <= x+dx && x+dx < H && 0 <= y+dy && y+dy < W){
                if(star[x+dx][y+dy] >= 0 && !iso[star[x+dx][y+dy]]){
                    int constellation = dsu.leader(star[x+dx][y+dy]);
                    if(C[constellation] != ci){ C[constellation] = ci; count++; }
                }
            }
        }
        chmax(maxmerge, count);
        chmin(minmerge, count);
    }

    i64 a = 0;
    rep(i,N) if(dsu.leader(i) == i && dsu.size(i) != 1) a++;

    i64 lb = a - max(1, maxmerge) + 1, ub = a - max(1, minmerge) + 1;

    //cout << "a = " << a << endl;
    //cout << "maxmerge = " << maxmerge << endl;
    //cout << "minmerge = " << minmerge << endl;


    int up_ub = 0;
    
    vector<vector<int>> sp(H, vector<int>(W, -1));
    rep(i,N) if(!iso[i]) sp[P[i].first][P[i].second] = D;
    rep(y,H) rep(x,W-1) chmax(sp[y][x+1], sp[y][x] - 1);
    rep(y,H) repr(x,W-1) chmax(sp[y][x], sp[y][x+1] - 1);
    rep(y,H-1) rep(x,W) chmax(sp[y+1][x], sp[y][x] - 1);
    repr(y,H-1) rep(x,W) chmax(sp[y][x], sp[y+1][x] - 1);
    vector<vector<int>> spiso(H, vector<int>(W, -1));
    rep(i,N) if(iso[i]) spiso[P[i].first][P[i].second] = D;
    rep(y,H) rep(x,W-1) chmax(spiso[y][x+1], spiso[y][x] - 1);
    rep(y,H) repr(x,W-1) chmax(spiso[y][x], spiso[y][x+1] - 1);
    rep(y,H-1) rep(x,W) chmax(spiso[y+1][x], spiso[y][x] - 1);
    repr(y,H-1) rep(x,W) chmax(spiso[y][x], spiso[y+1][x] - 1);
    rep(y,H) rep(x,W) if(spiso[y][x] >= 0 && spiso[y][x] != D && sp[y][x] < 0) up_ub++;

    //cout << "up_ub = " << up_ub << endl;
    if(up_ub){
        ub = a + 1;
        if(up_ub + N == H*W) lb = ub;
    }

    cout << lb << " " << ub << "\n";
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef NACHIA
    int T; cin >> T; for(int t=0; t<T; T!=++t?(cout<<'\n'),0:0)
    #endif
    testcase();
    return 0;
}
0