結果

問題 No.2696 Sign Creation
ユーザー 👑 NachiaNachia
提出日時 2024-03-22 22:59:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 78 ms / 2,500 ms
コード長 3,802 bytes
コンパイル時間 1,412 ms
コンパイル使用メモリ 118,512 KB
実行使用メモリ 7,680 KB
最終ジャッジ日時 2024-03-27 17:59:10
合計ジャッジ時間 3,044 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 2 ms
6,676 KB
testcase_05 AC 2 ms
6,676 KB
testcase_06 AC 2 ms
6,676 KB
testcase_07 AC 2 ms
6,676 KB
testcase_08 AC 3 ms
6,676 KB
testcase_09 AC 2 ms
6,676 KB
testcase_10 AC 3 ms
6,676 KB
testcase_11 AC 3 ms
6,676 KB
testcase_12 AC 3 ms
6,676 KB
testcase_13 AC 67 ms
6,676 KB
testcase_14 AC 25 ms
6,676 KB
testcase_15 AC 23 ms
6,676 KB
testcase_16 AC 60 ms
6,676 KB
testcase_17 AC 20 ms
6,676 KB
testcase_18 AC 13 ms
6,676 KB
testcase_19 AC 27 ms
6,676 KB
testcase_20 AC 4 ms
6,676 KB
testcase_21 AC 22 ms
6,676 KB
testcase_22 AC 25 ms
6,676 KB
testcase_23 AC 23 ms
6,676 KB
testcase_24 AC 23 ms
6,676 KB
testcase_25 AC 34 ms
6,676 KB
testcase_26 AC 22 ms
6,676 KB
testcase_27 AC 23 ms
6,676 KB
testcase_28 AC 17 ms
6,676 KB
testcase_29 AC 22 ms
6,676 KB
testcase_30 AC 22 ms
6,676 KB
testcase_31 AC 78 ms
7,680 KB
testcase_32 AC 2 ms
6,676 KB
testcase_33 AC 2 ms
6,676 KB
testcase_34 AC 2 ms
6,676 KB
testcase_35 AC 1 ms
6,676 KB
testcase_36 AC 2 ms
6,676 KB
testcase_37 AC 2 ms
6,676 KB
testcase_38 AC 2 ms
6,676 KB
testcase_39 AC 2 ms
6,676 KB
testcase_40 AC 2 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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