秋祭 | 静岡高校工学部



卬高杯


提出詳細

提出id提出時刻ユーザー名問題言語判定状況判定実行時間
1148462023-10-24 08:52:25hiikunZJcpp11/11TLE96

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
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<ld> B(N),T(M);
    for(ll i = 0;i < N;i++) cin >> B[i];
    sort(B.begin(),B.end());
    for(ll i = 0;i < M;i++) cin >> T[i];
    UnionFind UF(M + 100);
    for(ll i = 0;i < X + 100000;i++){
        ll u,v;
        cin >> u >> v;
        u--;
        v--;
        UF.unite(u,v);
    }
    ll ans = 0;
    for(ll i = 0;i < M;i++){
        ld dis = MAX;
        for(ll j = 0;j < N;j++){
            dis = min(dis,abs(B[j] - T[i]));
        }
        if(dis <= P) ans += UF.unite(i,M);
    }
    cout << ans << endl;
}

case1.txt TLE 96
case2.txt TLE 86
case3.txt TLE 86
case4.txt TLE 85
case5.txt TLE 85
case6.txt TLE 85
case9.txt TLE 86
case10.txt TLE 87
case11.txt TLE 87
case13.txt TLE 85
sample1.txt TLE 85
96 RE96 TLE
timeout: the monitored command dumped core
Segmentation fault