結果

問題 No.1170 Never Want to Walk
コンテスト
ユーザー Craft Boss
提出日時 2025-10-08 18:20:53
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,227 bytes
コンパイル時間 2,491 ms
コンパイル使用メモリ 100,660 KB
実行使用メモリ 15,940 KB
最終ジャッジ日時 2025-10-08 18:21:06
合計ジャッジ時間 7,958 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm>

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

class StationConnectivity {
private:
    std::vector<int> parent; // 根ノードの場合、値はグループのサイズ * (-1)

public:
    StationConnectivity(int num_station) {
        // 全要素を-1で初期化（各要素が独立したグループでサイズ1）
        parent.assign(num_station, -1);
    }

    // 経路圧縮ありの find 操作
    int find(int id) {
        if (parent[id] < 0) {
            return id;
        }
        // 経路圧縮
        return parent[id] = find(parent[id]);
    }

    // サイズによる統合 (Union by Size)
    void union_sets(int root1, int root2) {
        if (root1 == root2) {
            return;
        }

        // サイズの大きい方に小さい方を結合
        if (parent[root1] > parent[root2]) { // parent[i] は負の値なので、値が大きい(絶対値が小さい)方がサイズが小さい
            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; // 接続範囲の下限ポインタ
        int j_end = 0;   // 接続範囲の上限ポインタ

        for (int i = 0; i < num_station; ++i) {
            int x = xi[i];

            // 1. j_start を更新 (xi[i] - xi[j_start] <= B を満たすように)
            // Python: while j_start < i and x - xi[j_start] > B: j_start += 1
            while (j_start < i && x - xi[j_start] > B) {
                j_start++;
            }

            // 2. j_end を更新 (xi[i] - xi[j_end] >= A を満たすように)
            // Python: while j_end < i and x - xi[j_end] >= A: j_end += 1
            while (j_end < i && x - xi[j_end] >= A) {
                j_end++;
            }
            
            // 3. 範囲 [j_start, j_end) の要素に対して Union を実行
            for (int j = j_start; j < j_end; ++j) {
                int root_i = find(i);
                int root_j = find(j);
                
                if (root_i != root_j) {
                    union_sets(root_i, root_j);
                }
            }
        }
    }
    
    // 連結な駅の数を返す
    int countReachable(int id) {
        // parent[root] * -1 がサイズ
        return parent[find(id)] * -1;
    }
};

void solve() {
    // 1. 入力
    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];
    }

    // 2. Union-Findの実行 (O(N * α(N)))
    StationConnectivity railway(num_station);
    railway.union_stations(xi, A, B);

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

int main() {
    // 入出力高速化関数を呼び出し
    fast_io();
    solve();
    return 0;
}
0