結果

問題 No.33 アメーバがたくさん
コンテスト
ユーザー codershifth
提出日時 2015-07-23 09:39:14
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 3,286 bytes
コンパイル時間 1,716 ms
コンパイル使用メモリ 181,312 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-24 10:13:10
合計ジャッジ時間 2,234 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;

class UFTree {
    std::vector<int> par_;
    std::vector<int> rank_;
    int size_;
public:
    UFTree(int N) { init(N); }
    UFTree() {}
    ~UFTree() {}

    void init(int N) {
        par_.resize(N);
        rank_.resize(N, 0);
        for (int i = 0; i < N; ++i)
            par_[i] = i;
        size_ = N;
    }
    int find(int x) {
        assert(0 <= x && x < par_.size());
        if ( par_[x] == x )
            return x;
        else
            return ( par_[x] = find(par_[x]));
    }
    void unite(int x, int y) {
        assert(0 <= x && x < par_.size());
        assert(0 <= y && y < par_.size());
        x = find(x);
        y = find(y);
        if ( x == y )
            return;
        --size_;
        if ( rank_[x] < rank_[y] )
            par_[x] = y;
        else
        {
            par_[y] = x;
            if ( rank_[x] == rank_[y] )
                ++rank_[x];
        }
    }
    bool same(int x, int y) {
        return (find(x) == find(y));
    }
    size_t size() { return size_; }
    // find 経由で par を更新してからでないと par へのアクセスは危険
    int operator[](size_t i) { return find(i); }
};

class ManyAmeba {
public:
    void solve(void) {
            int N,D,T;
            cin>>N>>D>>T;
            vector<ll> X(N);
            REP(i,N)
                cin>>X[i];
            sort(RANGE(X));

            UFTree uft(N);
            // O(N^2*A)
            REP(i,N)
            FOR(j,i,N)
            {
                // 時間 T 以内で同じ座標に到達しうるもの同士をまとめる
                // 距離の差が D 倍なら T が十分に大きいとき同じ座標に到達する。
                // X[i],X[j] 双方から進んでくるとみなせるので距離の差の半分を T 時間内の
                // 移動できるなら条件を満たす。
                if (abs(X[i]-X[j])%D==0 && abs(X[i]-X[j])/D <= 2*T)
                    uft.unite(i,j);
            }
            map<int,pair<ll,ll>> group;
            // まとめたものの最大・最小位置を求める
            REP(i,N)
            {
                // 初期化
                if (!group.count(uft[i]))
                    group.emplace(piecewise_construct,
                                  forward_as_tuple(uft[i]),
                                  forward_as_tuple(X[i],X[i]));

                auto &rng = group[uft[i]];
                rng.first  = min(rng.first,  X[i]);
                rng.second = max(rng.second, X[i]);
            }
            ll sum = 0;
            // 計算
            for (auto g : group)
            {
                ll b,e;
                tie(b,e) = g.second;
                // 前後を埋める
                sum += 2*T;
                // 中間を埋める
                sum += ((e-b)/D+1);
            }
            cout<<sum<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new ManyAmeba();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0