#695615 (C++14) No.1668 Grayscale

提出ソース

結果

問題	No.1668 Grayscale
ユーザー	milkcoffee
提出日時	2021-09-03 22:16:50
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	9,723 bytes
コンパイル時間	5,140 ms
コンパイル使用メモリ	238,596 KB
実行使用メモリ	84,352 KB
最終ジャッジ日時	2024-05-09 04:35:38
合計ジャッジ時間	6,776 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	AC	5 ms 11,136 KB
testcase_02	AC	6 ms 11,120 KB
testcase_03	AC	6 ms 11,224 KB
testcase_04	WA	-
testcase_05	AC	4 ms 11,208 KB
testcase_06	WA	-
testcase_07	AC	226 ms 81,536 KB
testcase_08	AC	64 ms 19,072 KB
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	5 ms 11,260 KB
testcase_23	AC	5 ms 11,136 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
#define forin(in ,n) for(ll i=0; i<n; i++) cin>>in[i]
#define forout(out) for(ll i=0; i<(ll)out.size(); i++) cout<<out[i]<<endl
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep_up(i, a, n) for (ll i = a; i < n; ++i)
#define rep_down(i, a, n) for (ll i = a; i >= n; --i)
#define P pair<ll, ll>
#define pb push_back

#define all(v) v.begin(), v.end()
#define fi first
#define se second
#define vvvll vector<vector<vector<ll>>>
#define vvll vector<vector<ll>>
#define vll vector<ll>
#define pqll priority_queue<ll>
#define pqllg priority_queue<ll, vector<ll>, greater<ll>>

template<class T> using V = vector<T>;

constexpr ll INF = (1ll << 60);
constexpr ll mod = 1000000007;
//constexpr ll mod = 998244353;

constexpr double pi = 3.14159265358979323846;
template <typename T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
void pt(T val) {
    cout << val << "\n";
}
template <typename T>
void pt_vll(vector<T> &v) {
    ll vs = v.size();
    rep(i, vs) {
        cout << v[i];

        if (i == vs - 1)
            cout << "\n";
        else
            cout << " ";
    }
}
ll mypow(ll a, ll n) {
    ll ret = 1;
    if(n==0) return 1;
    if(a==0) return 0;
    rep(i, n) {
        if (ret > (ll)(9e18 + 10) / a) return -1;
        ret *= a;
    }
    return ret;
}
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

struct UnionFind {
    vector<ll> par,size;

    UnionFind(ll N) : par(N) { //最初はすべてが根であるとして初期化
        size.resize(N,1);
        for(ll i=0;i<N;i++) par[i] = i;
    }

    ll root(ll x){ //データxの木の根を再帰で得る
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(ll x, ll y){ //xとyの木を併合
        ll rx = root(x);
        ll ry = root(y);
        if(rx == ry) return; //同じ木にあるときはそのまま
        if(size[rx]>size[ry]){
            par[ry]=rx;
            size[rx] += size[ry];
        }else{
            par[rx] = ry;
            size[ry] += size[rx];
        }
        return;
    }

    bool same(ll x, ll y){ //2つのデータx,yが属する木が同じならtrue
        ll rx = root(x);
        ll ry = root(y);
        return rx == ry;
    }

    ll treesize(ll x){return size[root(x)];}
};

const int MAX = 2010000;
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
long long COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

/* SegTreeLazy<X,M>(n,fx,fa,fm,ex,em): モノイド(集合X, 二項演算fx,fa,fm, 単位元ex,em)についてサイズnで構築
    set(int i, X x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
    update(i,x): i 番目の要素を x に更新。O(log(n))
    query(a,b):  [a,b) 全てにfxを作用させた値を取得。O(log(n))
*/
template <typename X, typename M>
struct SegTreeLazy {
    using FX = function<X(X, X)>;
    using FA = function<X(X, M)>;
    using FM = function<M(M, M)>;
    int n;
    FX fx;
    FA fa;
    FM fm;
    const X ex;
    const M em;
    vector<X> dat;
    vector<M> lazy;
    SegTreeLazy(int n_, FX fx_, FA fa_, FM fm_, X ex_, M em_)
        : n(), fx(fx_), fa(fa_), fm(fm_), ex(ex_), em(em_), dat(n_ * 4, ex), lazy(n_ * 4, em) {
        int x = 1;
        while (n_ > x) x *= 2;
        n = x;
    }

    void set(int i, X x) { dat[i + n - 1] = x; }
    void build() {
        for (int k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);
    }

    /* lazy eval */
    void eval(int k) {
        if (lazy[k] == em) return;  // 更新するものが無ければ終了
        if (k < n - 1) {            // 葉でなければ子に伝搬
            lazy[k * 2 + 1] = fm(lazy[k * 2 + 1], lazy[k]);
            lazy[k * 2 + 2] = fm(lazy[k * 2 + 2], lazy[k]);
        }
        // 自身を更新
        dat[k] = fa(dat[k], lazy[k]);
        lazy[k] = em;
    }

    void update(int a, int b, M x, int k, int l, int r) {
        eval(k);
        if (a <= l && r <= b) {  // 完全に内側の時
            lazy[k] = fm(lazy[k], x);
            eval(k);
        } else if (a < r && l < b) {                     // 一部区間が被る時
            update(a, b, x, k * 2 + 1, l, (l + r) / 2);  // 左の子
            update(a, b, x, k * 2 + 2, (l + r) / 2, r);  // 右の子
            dat[k] = fx(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    void update(int a, int b, M x) { update(a, b, x, 0, 0, n); }

    X query_sub(int a, int b, int k, int l, int r) {
        eval(k);
        if (r <= a || b <= l) {  // 完全に外側の時
            return ex;
        } else if (a <= l && r <= b) {  // 完全に内側の時
            return dat[k];
        } else {  // 一部区間が被る時
            X vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            X vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return fx(vl, vr);
        }
    }
    X query(int a, int b) { return query_sub(a, b, 0, 0, n); }
};

/*
    using X = ll;
    using M = ll;
    auto fx = [](X x1, X x2) -> X { return min(x1, x2); };
    auto fa = [](X x, M m) -> X { return m; };
    auto fm = [](M m1, M m2) -> M { return m2; };
    int ex = numeric_limits<int>::max();
    int em = numeric_limits<int>::max();
    SegTreeLazy<X, M> rmq(n, fx, fa, fm, ex, em);

    rep(i,n){
        rmq.set(i,0);
    }
    rmq.build(); //設置 

*/

/* BIT: RAQ対応BIT
    初期値は a_1 = a_2 = ... = a_n = 0
    ・add(l,r,x): [l,r) に x を加算する
    ・sum(i): a_1 + a_2 + ... + a_i を計算する
    計算量は全て O(logn)
*/
template <typename T>
struct BIT {
    int n;             // 要素数
    vector<T> bit[2];  // データの格納先
    BIT(int n_) { init(n_); }
    void init(int n_) {
        n = n_ + 1;
        for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
    }
 
    void add_sub(int p, int i, T x) {
        for (int idx = i; idx < n; idx += (idx & -idx)) {
            bit[p][idx] += x;
        }
    }
    void add(int l, int r, T x) {  // [l,r) に加算
        add_sub(0, l, -x * (l - 1));
        add_sub(0, r, x * (r - 1));
        add_sub(1, l, x);
        add_sub(1, r, -x);
    }
 
    T sum_sub(int p, int i) {
        T s(0);
        for (int idx = i; idx > 0; idx -= (idx & -idx)) {
            s += bit[p][idx];
        }
        return s;
    }
    T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i; }
};



vector<ll> enum_div(ll n){    //約数全列挙
    vector<ll> ret;
    for(ll i = 1 ; i*i <= n ; ++i){
        if(n%i == 0){
            ret.push_back(i);
            if(i*i != n){
                ret.push_back(n/i);
            }
        }
    }
    return ret;
}

void make_prime(vector<ll> &ret, ll n) { //素因数分解
    ll x = n;
    for (ll i = 2; i * i <= x; i++) {
        while (n % i == 0) {
            n /= i;
            ret.push_back(i);
        }
    }
    if (n != 1) {
        ret.push_back(n);
    }
    return;
}

vector<bool> prime(1000010, true);
vector<ll> pri(1000010);
vector<bool> isprime(int N) { //素数判定
    if (N >= 0) prime[0] = false;
    if (N >= 1) prime[1] = false;
    for (ll i = 2; i * i <= N; i++) {
        if (!prime[i]) {
            continue;
        }
        for (ll j = i * i; j <= N; j += i) {
            if(prime[j]) pri[j]=i;
            prime[j] = false;
        }
    }
    return prime;
}

//素因数分解: void make_prime(vector<ll> &ret, ll n)
//素数判定: vector<bool> isprime(int N)
//約数全列挙: vector<ll> enum_div(ll n)

void solve(){
    ll n,m,k,h,w,cnt=0,sum=0,ans=0;
    cin>>h>>w>>n;
    vvll G(n);
    vvll a(h,vll(w));
    rep(i,h){
        rep(j,w){
            cin>>a[i][j];
            a[i][j]--;
        }
    }
    rep(i,h){
        rep(j,w-1){
            ll x,y;
            x=a[i][j];
            y=a[i][j+1];
            if(x==y) continue;
            if(x>y) swap(x,y);
            G[x].push_back(y);
        }
    }
    rep(i,h-1){
        rep(j,w){
            ll x,y;
            x=a[i][j];
            y=a[i+1][j];
            if(x==y) continue;
            if(x>y) swap(x,y);
            G[x].push_back(y);
        }
    }
    vll color(n+1);
    color[n-1]=1;
    rep_down(i,n-2,0){
        ll x=n;
        for(auto e:G[i]){
            chmin(x,e);
        }
        color[i]=color[x]+1;
    }
    ans=color[0];
    cout<<ans<<endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //cout << fixed << setprecision(16);
    //ll T;
    //cin>>T;
    //rep(ca,T) 
    solve();
    
}

yukicoder

結果

テストケース

ソースコード