結果

問題 No.1668 Grayscale
ユーザー sapphire__15sapphire__15
提出日時 2021-09-03 23:07:33
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,763 bytes
コンパイル時間 1,702 ms
コンパイル使用メモリ 149,504 KB
実行使用メモリ 132,316 KB
最終ジャッジ日時 2024-05-09 06:40:42
合計ジャッジ時間 5,954 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 WA -
testcase_05 RE -
testcase_06 WA -
testcase_07 AC 556 ms
132,316 KB
testcase_08 RE -
testcase_09 WA -
testcase_10 RE -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 RE -
testcase_18 RE -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 2 ms
6,940 KB
testcase_23 AC 3 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <climits>
#include <cmath>
#include <complex>
#include <functional>
#include <cassert>
#include <stack>
#include <numeric>
#include <iomanip>
#include <limits>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <cstring>

typedef long long ll;
typedef std::pair<int, int> Pii;
typedef std::pair<ll, ll> Pll;
typedef std::pair<double, double> Pdd;

#define rip(_i, _n, _s) for (int _i = (_s); _i < (int)(_n); _i++)
#define all(_l) _l.begin(), _l.end()
#define rall(_l) _l.rbegin(), _l.rend()
#define MM << " " <<

template<typename _T>
using MaxHeap = std::priority_queue<_T>;
template<typename _T>
using MinHeap = std::priority_queue<_T, std::vector<_T>, std::greater<_T>>;

template<typename _T>
inline bool chmax(_T &_l, const _T _b) {
    if (_b > _l) {
        _l = _b;
        return true;
    }
    return false;
}
template<typename _T>
inline bool chmin(_T &_l, const _T _b) {
    if (_l > _b) {
        _l = _b;
        return true;
    }
    return false;
}

template<typename _T>
void vdeb(const std::vector<_T> &bb) {
    for (unsigned int i = 0;i < bb.size();i++) {
        if (i == bb.size() - 1) std::cout << bb[i];
        else std::cout << bb[i] << ' ';
    }
    std::cout << '\n';
}
template<typename _T>
void vdeb(const std::vector<std::vector<_T>> &bb) {
    for (unsigned int i = 0;i < bb.size();i++) {
        std::cout << i << ": ";
        vdeb(bb[i]);
    }
    std::cout << '\n';
}

class UnionFind {
    int _n;
    int _size;
    std::vector<int> par_size;

    public:
    UnionFind() :_n(0), _size(0){}
    UnionFind(int n) : _n(n), _size(n), par_size(n, -1) {}

    int unite(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        a = root(a), b = root(b);
        if(a == b) return a;
        _size--;
        if(-par_size[a] < -par_size[b]) {
            par_size[b] += par_size[a];
            return par_size[a] = b;
        }
        else {
            par_size[a] += par_size[b];
            return par_size[b] = a;
        }
    }

    int root(int a) {
        assert(0 <= a && a < _n);
        if(par_size[a] < 0) return a;
        return par_size[a] = root(par_size[a]); 
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return root(a) == root(b);
    }

    int size(int a) {
        assert(0 <= a && a< _n);
        return -par_size[root(a)];
    }

    int size() {return _size;}

    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] = root(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;
    }
};

using namespace std;

int dx[] = {0, 1, 0, -1, 0};

int main() {
    int h, w, n; cin >> h >> w >> n;
    vector<vector<int>> da(h, vector<int>(w));
    rip(i,h,0) rip(j,w,0) cin >> da[i][j];
    auto in_grid = [&](int x, int y) {
        return 0 <= x && x < h && 0 <= y && y < w;
    };
    auto to_int = [&](int x, int y) {
        return x*w + h;
    };
    UnionFind uf(h*w);
    rip(i,h,0) rip(j,w-1,0) if(da[i][j] == da[i][j+1]) {
        uf.unite(to_int(i, j), to_int(i, j+1));
    }
    rip(i,h-1,0) rip(j,w,0) if(da[i][j] == da[i+1][j]) {
        uf.unite(to_int(i, j), to_int(i+1, j));
    }
    vector<vector<int>> to_node(h, vector<int>(w));
    auto g = uf.groups();
    rip(i,g.size(),0) {
        for(auto j : g[i]) to_node[j/w][j%w] = i;
    }
    vector<vector<int>> to(g.size());
    vector<int> ot(g.size());
    rip(i,h,0) rip(j,w,0) rip(k,4,0) {
        int nx = i+dx[k], ny = j + dx[k+1];
        if(in_grid(nx, ny) && da[i][j] > da[nx][ny]) {
            to[to_node[i][j]].push_back(to_node[nx][ny]);
            ot[to_node[nx][ny]]++;
        }
    }
    queue<int> q;
    rip(i,ot.size(),0) if(ot[i] == 0) q.push(i);
    vector<int> pot(to.size(), 1);
    int ans = 1;
    while(!q.empty()) {
        auto now = q.front(); q.pop();
        ans = pot[now];
        for(auto &i : to[now]){
            ot[i]--;
            if(ot[i] == 0) {
                q.push(i);
                pot[i] = pot[now] + 1;
            }
        }
    }
    cout << ans << endl;
}
0