結果

問題 No.1170 Never Want to Walk
ユーザー Craft Boss
提出日時 2025-10-08 18:22:46
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,941 bytes
コンパイル時間 1,992 ms
コンパイル使用メモリ 89,860 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-08 18:22:51
合計ジャッジ時間 4,670 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other AC * 1 WA * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>

// 入出力の高速化
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

class StationConnectivity {
private:
    std::vector<int> parent; 

public:
    StationConnectivity(int num_station) {
        parent.assign(num_station, -1);
    }

    int find(int id) {
        if (parent[id] < 0) {
            return id;
        }
        return parent[id] = find(parent[id]);
    }

    void union_sets(int root1, int root2) {
        if (root1 == root2) {
            return;
        }
        if (parent[root1] > parent[root2]) { 
            std::swap(root1, root2);
        }
        parent[root1] += parent[root2];
        parent[root2] = root1;
    }

    void union_stations(const std::vector<int>& xi, int A, int B) {
        int num_station = xi.size();
        int j_start = 0; 

        // j_endポインタを廃止し、Unionのループと統合します。
        // これにより、接続のループ処理がシンプルになり、コンパイラの最適化が働きやすくなります。
        for (int i = 0; i < num_station; ++i) {
            int x = xi[i];

            // 1. j_start を更新 (xi[i] - xi[j_start] <= B を満たすように)
            // 接続可能な要素の最初のインデックスを探す。
            while (j_start < i && x - xi[j_start] > B) {
                j_start++;
            }

            // 2. 接続可能なすべての要素に対して Union を実行
            // j_endの代わりに、j=i-1からj=j_startまで逆方向にループします。
            // 範囲は [j_start, i-1] のうち、xi[i] - xi[j] >= A を満たすもの。
            for (int j = i - 1; j >= j_start; --j) {
                // 距離がA未満になったら、それより小さいjはすべてA未満なのでループを抜ける
                if (x - xi[j] < A) {
                    break; 
                }
                
                // Union-Findの操作
                int root_i = find(i);
                int root_j = find(j);
                
                if (root_i != root_j) {
                    union_sets(root_i, root_j);
                    // ルートが結合されたので、iの新しいルートを取得
                    root_i = find(i);
                }
            }
        }
    }
    
    int countReachable(int id) {
        return parent[find(id)] * -1;
    }
};

void solve() {
    int num_station, A, B;
    if (!(std::cin >> num_station >> A >> B)) return;

    std::vector<int> xi(num_station);
    for (int i = 0; i < num_station; ++i) {
        std::cin >> xi[i];
    }

    StationConnectivity railway(num_station);
    railway.union_stations(xi, A, B);

    for (int i = 0; i < num_station; ++i) {
        std::cout << railway.countReachable(i) << "\n";
    }
}

int main() {
    fast_io();
    solve();
    return 0;
}
0