結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
|
提出日時 | 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 |
ソースコード
#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; }