結果
問題 | No.1170 Never Want to Walk |
ユーザー |
![]() |
提出日時 | 2020-08-14 21:45:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 68 ms / 2,000 ms |
コード長 | 1,361 bytes |
コンパイル時間 | 3,240 ms |
コンパイル使用メモリ | 196,564 KB |
最終ジャッジ日時 | 2025-01-12 23:33:44 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template <class T> using vec = vector<T>; template <class T> using vvec = vector<vec<T>>; class UnionFind{ private: vec<int> p,s; int cnt; public: UnionFind(){} UnionFind(int N):cnt(N),s(N,1),p(N){ iota(p.begin(),p.end(),0); } int find(int x){ if(p[x]==x) return x; else return p[x] = find(p[x]); } void unite(int x,int y){ x = find(x); y = find(y); if(x==y) return; if(s[x]>s[y]) swap(x,y); p[x] = y; s[y] += s[x]; cnt--; } bool is_same_set(int x,int y) {return find(x)==find(y);} int size(int x) {return s[find(x)];} int compnents_number(){return cnt;} }; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N,A,B; cin >> N >> A >> B; vec<int> X(N); for(auto& x:X) cin >> x; UnionFind uf(N); int l = 0,r = 0; for(int i=0;i<N;i++){ if(l<i) l = i; while(l<N && abs(X[i]-X[l])<A){ l++; } // cerr << i << " " << l << "\n"; if(l==N) break; if(r<l) r = l+1; if(abs(X[i]-X[l])>B) continue; uf.unite(i,l); while(r<N && abs(X[i]-X[r])<=B){ uf.unite(i,r); r++; } } for(int i=0;i<N;i++) cout << uf.size(i) << "\n"; }