結果

問題 No.2696 Sign Creation
コンテスト
ユーザー applejam
提出日時 2025-09-10 13:46:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 112 ms / 2,500 ms
コード長 2,437 bytes
コンパイル時間 4,476 ms
コンパイル使用メモリ 204,148 KB
実行使用メモリ 10,240 KB
最終ジャッジ日時 2025-09-10 13:46:49
合計ジャッジ時間 7,059 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vmi = vector<mint>;
using vvmi = vector<vmi>;
using vvvmi = vector<vvmi>;
#define all(a) (a).begin(), (a).end()
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
using p = pair<int, int>;

int main(){

    int h, w, n, d; cin >> h >> w >> n >> d;
    vector<vector<p>> mh(d);
    rep(i, d){
        int s = i+1;
        rep2(j, -s, s+1){
            mh[i].push_back({j, s-abs(j)});
            if(s-abs(j)!=0){
                mh[i].push_back({j, abs(j)-s});
            }
        }
    }
    vvi grid(h, vi(w, 0));
    rep(i, n){
        int x, y; cin >> x >> y;
        grid[x-1][y-1] = 1;
    }
    dsu ds(h*w);
    rep(i, h*w){
        int j = i/w, k = i%w;
        if(grid[j][k] == 0)continue;
        for(auto u : mh){
            for(auto v : u){
                int a = j+v.first, b = k + v.second;
                if(a < 0 || a >= h || b < 0 || b >= w)continue;
                if(grid[a][b] == 1){
                    ds.merge(i, a*w+b);
                }
            }
        }
    }
    int size = 0;
    for(auto v : ds.groups()){
        if(v.size() > 1)size++;
    }
    int ansa = size, ansb = size;

    rep(i, h*w){
        int j = i/w, k = i%w;
        set<int> mg;
        int dp = 0;
        if(grid[j][k] == 1)continue;
        for(auto u : mh){
            for(auto v : u){
                int a = j+v.first, b = k + v.second;
                if(a < 0 || a >= h || b < 0 || b >= w)continue;
                if(grid[a][b] == 1){
                    int l = ds.leader(a*w+b);
                    if(ds.size(a*w+b) == 1){
                        dp = 1;
                    }else{
                        mg.insert(l);
                    }
                }
            }
        }
        int tmp = size;
        if(mg.size()>1){
            tmp -= mg.size()-1;
        }else if(dp==1)tmp++;
        ansa = min(ansa, tmp);
        ansb = max(ansb, tmp);
    }
    cout << ansa << " " << ansb << endl;
    return 0;
}
0