結果
問題 | No.1170 Never Want to Walk |
ユーザー |
![]() |
提出日時 | 2020-08-14 21:46:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 387 ms / 2,000 ms |
コード長 | 1,543 bytes |
コンパイル時間 | 2,342 ms |
コンパイル使用メモリ | 199,056 KB |
最終ジャッジ日時 | 2025-01-12 23:34:12 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; template <class Abel> class UnionFind{ vector<int> par_, weight_; public: UnionFind(size_t n){ par_.assign(n, -1); weight_.assign(n, 0); } int root(int x){ if (par_[x] < 0) { return x; }else{ int res = root(par_[x]); weight_[x] += weight_[par_[x]]; return par_[x] = res; } } int weight(int x){ root(x); return weight_[x]; } int weight(int x, int y){ return weight(y) - weight(x); } int size(int x){ return -par_[root(x)]; } bool IsSame(int x, int y){ return root(x) == root(y); } void Merge(int x, int y, Abel w){ w += weight(x); w -= weight(y); x = root(x); y = root(y); if (x == y) return; if (size(x) < size(y)) { w = -w; swap(x, y); } par_[x] += par_[y]; par_[y] = x; weight_[y] = w; } }; int main(){ int n, a, b; cin >> n >> a >> b; vector<int> X(n); copy_n(istream_iterator<int>(cin), n, X.begin()); int l = 0, r = 0; UnionFind<int> uf(n); for (int i = 0; i < n; i++){ while (r < n and X[r] - X[i] <= b) r++; while (l < n and X[l] - X[i] < a) l++; for (int j = l; j < r; j++) uf.Merge(i, j, 0); l = r - 1; } for (int i = 0; i < n; i++) cout << uf.size(i) << endl; }