提出詳細

提出id	提出時刻	ユーザー名	問題	言語	判定状況	判定	実行時間
114792	2023-10-24 08:08:37	hiikunZ	J	cpp	11/11	AC	8

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const ll MAX = 1e18;
struct UnionFind{
    vector<ll> par;
    ll S;
    UnionFind(ll N):par(N,-1){ S = N; };
    ll root(ll A){
        if(par[A] < 0) return A;
        return par[A] = root(par[A]);
    }
    bool same(ll A,ll B){
        return root(A) == root(B);
    }
    bool unite(ll A,ll B){
        ll a = root(A),b = root(B);
        if(a == b) return false;
        if(par[a] > par[b]) swap(a,b);
        par[a] += par[b];
        par[b] = a;
        S--;
        return true;
    }
    ll size(ll A){
        return par[root(A)] * -1;
    }
    ll size(){
        return S;
    }
};

int main(){
    ll N,M,X,P;
    cin >> N >> M >> X >> P;
    vector<ll> B(N),T(M);
    for(ll i = 0;i < N;i++) cin >> B[i];
    B.emplace_back(-MAX);
    B.emplace_back(MAX);
    sort(B.begin(),B.end());
    for(ll i = 0;i < M;i++) cin >> T[i];
    UnionFind UF(M + 1);
    for(ll i = 0;i < X;i++){
        ll u,v;
        cin >> u >> v;
        u--;
        v--;
        UF.unite(u,v);
    }
    ll ans = 0;
    for(ll i = 0;i < M;i++){
        ll dis = MAX;
        auto it = lower_bound(B.begin(),B.end(),T[i]);
        dis = min(dis,abs(T[i] - *it));
        it--;
        dis = min(dis,abs(T[i] - *it));
        if(dis <= P) ans += UF.unite(i,M);
    }
    cout << ans << endl;
}

case1.txt AC 2
case2.txt AC 3
case3.txt AC 4
case4.txt AC 6
case5.txt AC 7
case6.txt AC 8
case9.txt AC 7
case10.txt AC 7
case11.txt AC 8
case13.txt AC 7
sample1.txt AC 7
8 AC8 AC