結果

問題 No.3252 Constrained Moving
コンテスト
ユーザー jiyujin816
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#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();
    }
}
0