結果
問題 |
No.3252 Constrained Moving
|
ユーザー |
|
提出日時 | 2025-09-05 21:26:46 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 4,526 bytes |
コンパイル時間 | 3,437 ms |
コンパイル使用メモリ | 289,044 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-09-05 21:26:57 |
合計ジャッジ時間 | 5,739 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
//#define _GLIBCXX_DEBUG #include <bits/stdc++.h> /*多倍長整数 #include <boost/multiprecision/cpp_dec_float.hpp> #include <boost/multiprecision/cpp_int.hpp> namespace mp = boost::multiprecision; // 任意長整数型 using Bint = mp::cpp_int; //仮数部が10進数で1024桁の浮動小数点数型(TLEしたら小さくする) using Real = mp::number<mp::cpp_dec_float<1024>>; */ using namespace std; using ll=long long; using ull=unsigned long long; using ld=long double; using P=pair<ll,ll>; const ll INF=1e17; const vector<ll> dx={0,0,1,-1,1,1,-1,-1}; const vector<ll> dy={1,-1,0,0,1,-1,-1,1}; const vector<char> dirs={'>','<','v','^'}; #define rep1(a) for(ll i = 0; i < a; ++i) #define rep2(i, a) for(ll i = 0; i < a; ++i) #define rep3(i, a, b) for(ll i = a; i < b; ++i) #define rep4(i, a, b, c) for(ll i = a; i < b; i += c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() template <typename T1,typename T2> ostream& operator<<(ostream &os,pair<T1,T2> &pai){ return os<<"("<<pai.first<<","<<pai.second<<") "; } template<typename T> ostream& operator<<(ostream &os,vector<T> vec){ for(auto val:vec){ os<<val<<" "; } return os<<"\n"; } template<typename T,typename T2> istream& operator>>(istream &is,pair<T,T2> &pai){ is>>pai.first>>pai.second; return is; } template<typename T> istream& operator>>(istream &is,vector<T> &vec){ for(int i=0;i<(int)vec.size();i++){ is>>vec[i]; } return is; } void set_cout(){ cout<<fixed<<setprecision(15); } template <typename T> void print(const T &vec){ int i=0; for(auto val:vec){ cout<<i<<":"<<val<<","; i++; } cout<<'\n'; } template<typename T> void print2(const vector<vector<T>> &vec){ int i=0; for(auto v:vec){ cout<<i<<": "; for(auto a:v){ cout<<a<<" "; } i++; cout<<'\n'; } } template<class T> void chmin(T &a,T b){ if(a>b){ a=b; } return; } template<class T> void chmax(T &a,T b){ if(a<b){ a=b; } return; } struct ob3{ ll a,b,c; bool operator<(const ob3 &o) const{ return a<o.a; } bool operator>(const ob3 &o) const{ return a>o.a; } }; struct UnionFind{ int N; vector<int> par,rank,siz; int cnt; UnionFind(int n){ assert(0<=n); N=n; par.resize(N,-1); rank.resize(N,0); siz.resize(N,1); cnt=n; } int leader(int x){ assert(0<=x && x<N); if(par[x]==-1){ return x; }else{ return par[x]=leader(par[x]); } } bool same(int x,int y){ assert(0<=x && x<N); assert(0<=y && y<N); return leader(x)==leader(y); } int merge(int x,int y){ assert(0<=x && x<N); assert(0<=y && y<N); int rx=leader(x); int ry=leader(y); if(rx==ry){ return rx; } if(rank[rx]<rank[ry]){ swap(rx,ry); } par[ry]=rx; if(rank[rx]==rank[ry]){ rank[rx]++; } siz[rx]+=siz[ry]; cnt--; return leader(x); } int size(int x){ assert(0<=x && x<N); return siz[leader(x)]; } int size(){ return N; } void insert(){ rank.push_back(0); par.push_back(-1); siz.push_back(1); cnt++; N++; return; } vector<vector<int>> groups(){ vector<vector<int>> member(N); for(int v=0;v<N;v++){ member[leader(v)].push_back(v); } vector<vector<int>> res; for(int v=0;v<N;v++){ if(!member[v].empty()){ res.push_back(member[v]); } } return res; } int group_cnt(){ return cnt; } }; void solve(){ ll N,S,T,K; cin>>N>>S>>T>>K; S--;T--; vector<ll> A(N); cin>>A; UnionFind uf(N); int minApos=min_element(all(A))-A.begin(); rep(i,N){ if(A[i]+A[minApos]<=K){ uf.merge(i,minApos); } } if(uf.same(S,T)){ if(A[S]+A[T]<=K){ cout<<1; }else{ cout<<2; } }else{ cout<<-1; } } int main(){ cin.tie(0)->sync_with_stdio(0); int T=1; //cin>>T; while(T--){ solve(); } }