結果

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

ソースコード

diff # 

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

/**
 * @brief 駅の連結情報を管理するUnion-Findデータ構造を実装したクラス
 */
class StationConnectivity {
private:
    // 各要素の親を格納する配列。
    // 負の値はその要素が根であることを示し、その絶対値が集合のサイズを表す。
    std::vector<int> parent;

public:
    /**
     * @brief コンストラクタ
     * @param num_station 駅の総数
     */
    StationConnectivity(int num_station) : parent(num_station, -1) {}

    /**
     * @brief 指定された駅が属する集合の根（代表駅）を見つける
     * @param id 駅のインデックス
     * @return int 集合の根のインデックス
     */
    int find(int id) {
        // 自身が根であれば、自身のインデックスを返す
        if (parent[id] < 0) {
            return id;
        }
        // 親を再帰的にたどり、経路圧縮を行う
        return parent[id] = find(parent[id]);
    }

    /**
     * @brief 2つの駅が属する集合を1つに統合する
     * @param id1 駅1のインデックス
     * @param id2 駅2のインデックス
     */
    void unite(int id1, int id2) {
        int root1 = find(id1);
        int root2 = find(id2);

        if (root1 != root2) {
            // サイズが小さい集合を大きい集合に統合する (union by size)
            if (parent[root1] > parent[root2]) {
                std::swap(root1, root2); // root1がより大きい集合の根になるように
            }
            // サイズを更新
            parent[root1] += parent[root2];
            // 小さい方の集合の根を大きい方の根に接続
            parent[root2] = root1;
        }
    }

    /**
     * @brief 指定された駅から到達可能な駅の総数を返す
     * @param id 駅のインデックス
     * @return int 到達可能な駅の総数
     */
    int countReachable(int id) {
        return -parent[find(id)];
    }
};

/**
 * @brief メイン処理
 */
int main() {
    // C++の標準入出力の高速化
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // --- 入力処理 ---
    int num_station, A, B;
    std::cin >> num_station >> A >> B;

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

    // --- メインロジック ---
    StationConnectivity railway(num_station);

    // 全ての駅のペアをチェックし、条件を満たすなら接続する (O(N^2)の処理)
    for (int i = 0; i < num_station; ++i) {
        for (int j = 0; j < i; ++j) {
            int distance = xi[i] - xi[j];
            if (distance >= A && distance <= B) {
                railway.unite(i, j);
            }
        }
    }

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

    return 0;
}
0