#1161212 (C++23(gnu拡張)) No.3517 Snake Kunekune Graph

• 問題: No.3517 Snake Kunekune Graph
• ユーザー: Yoyoyo8128
• 提出日時: 2026-04-24 14:29:42
• 言語: C++23(gnu拡張) (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 5,615 bytes
• コンパイル時間: 3,236 ms
• コンパイル使用メモリ: 365,752 KB
• 実行使用メモリ: 46,720 KB
• 最終ジャッジ日時: 2026-04-24 20:57:18
• 合計ジャッジ時間: 13,486 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_1

ファイルパターン	結果
sample	AC * 2
other	AC * 11 WA * 34

ソースコード

#pragma region Yoyoyo

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using i128t=__int128_t;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const string Yes="Yes";
const string No="No";
const long long inf=1ll<<60;

#ifndef LOCAL
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr);
#define print(s) cout<<s<<endl;

template<typename T>
inline bool chmax(T &a,T b){return ((a<b)?(a=b,true):(false));}
template<typename T>
inline bool chmin(T &a,T b){return ((a>b)?(a=b,true):(false));}
template<typename T>
ll sum(const T&a){return accumulate(all(a),0LL);}

template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U>&p){
    os<<p.first<<" "<<p.second;
    return os;
}

template<typename T,typename U>
istream &operator>>(istream &is,pair<T,U>&p){
    is>>p.first>>p.second;
    return is;
}

template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    int s=v.size();
    for(int i=0;i<s;i++){
        os<<(i?" ":"")<<v[i];
    }
    return os;
}

template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(auto &x:v){
        is>>x;
    }
    return is;
}

template<typename T>
ostream &operator<<(ostream &os,const vector<vector<T>>&v){
    int s=v.size();
    for(int i=0;i<s;i++){
        os<<v[i]<<endl;
    }
    return os;
}

template<typename T>
ostream &operator<<(ostream &os,const vector<vector<vector<T>>>&v){
    int s=v.size();
    for(int i=0;i<s;i++){
        os<<"i = "<<i<<endl;
        os<<v[i];
    }
    return os;
}

#ifdef LOCAL
template<class... Args>
void debug_out(Args... args){
    int _i=0;
    ((cerr<<(_i++?", ":" ")<<args), ...);
    cerr<<"\n";
}
#define debug(...){\
    cerr<<"["<<#__VA_ARGS__<<"]:";\
    debug_out(__VA_ARGS__);\
}
#else
#define debug(...)
#endif

#pragma endregion Yoyoyo


ll mod=998244353;

// UnionFind
struct UnionFind
{
    vector<long long> par, rank, siz;
    // 構造体の初期化
    UnionFind(long long n) : par(n, -1), rank(n, 0), siz(n, 1) {}

    // 根を求める
    long long root(long long x)
    {
        if (par[x] == -1)
            return x; // x が根の場合は x を返す
        else
            return par[x] = root(par[x]); // 経路圧縮
    }

    // x と y が同じグループに属するか (= 根が一致するか)
    bool same(long long x, long long y)
    {
        return root(x) == root(y);
    }

    // x を含むグループと y を含むグループを併合する
    bool unite(long long x, long long y)
    {
        int rx = root(x), ry = root(y); // x 側と y 側の根を取得する
        if (rx == ry)
            return false; // すでに同じグループのときは何もしない
        // union by rank
        if (rank[rx] < rank[ry])
            swap(rx, ry); // ry 側の rank が小さくなるようにする
        par[ry] = rx;     // ry を rx の子とする
        if (rank[rx] == rank[ry])
            rank[rx]++;     // rx 側の rank を調整する
        siz[rx] += siz[ry]; // rx 側の siz を調整する
        return true;
    }

    // x を含む根付き木のサイズを求める
    long long size(long long x)
    {
        return siz[root(x)];
    }
};


int main(){
    faster;
    ll N,M,X,K;
    cin>>N>>M>>X>>K;
    {
        assert(2<=N && N<=200000);
        assert(1<=M && M<=N*(N-1)/2 && M<=200000);
        assert(1<=X && X<=1000000000);
        assert(2<=K && K<=N);
    }
    vector<ll>A(N);
    cin>>A;
    vector<vector<pii>>G(N);
    vector<int>U(M),V(M);
    for(int i=0;i<M;i++){
        int u,v;
        cin>>u>>v;
        u--;v--;
        U[i]=u;V[i]=v;
        if(abs(A[u]-A[v])>X)continue;
        G[u].pb(mp(v,i));
        G[v].pb(mp(u,i));
    }
    for(int i=0;i<N;i++)sort(all(G[i]),[&A](pii l,pii r){return A[l.fi]<A[r.fi];});
    if(K==2){
        UnionFind uf(N);
        for(int i=0;i<N;i++){
            for(auto e:G[i])uf.unite(i,e.fi);
        }
        ll ans=0;
        for(int i=0;i<N;i++){
            if(uf.root(i)!=i)continue;
            ans+=uf.size(i)*(uf.size(i)-1);
        }
        print(ans);
        exit(0);
    }
    UnionFind uf(2*N);
    vector<ll>bg(N,inf),sm(N,-inf);
    for(int i=0;i<M;i++){
        if(abs(A[U[i]]-A[V[i]])>K)continue;
        if(A[U[i]]<A[V[i]]){
            uf.unite(U[i],V[i]+N);
            chmin(bg[U[i]],A[V[i]]);
            chmax(sm[V[i]],A[U[i]]);
        }else{
            uf.unite(U[i]+N,V[i]);
            chmin(bg[V[i]],A[U[i]]);
            chmax(sm[U[i]],A[V[i]]);
        }
    }
    for(int i=0;i<N;i++){
        if(bg[i]-sm[i]<=K)uf.unite(i,i+N);
    }
    debug("safe");
    vector<ll>cnt(2*N);
    map<pii,ll>cnt2;
    for(int i=0;i<2*N;i++){
        debug(uf.root(i));
    }
    for(int i=0;i<N;i++){
        if(uf.same(i,i+N)){
            cnt[uf.root(i)]++;
        }else{
            int a=uf.root(i),b=uf.root(i+N);
            if(a>b)swap(a,b);
            cnt[a]++;
            cnt[b]++;
            
            cnt2[mp(a,b)]++;
        }
    }
    ll ans=0;
    for(int i=0;i<N;i++){
        if(uf.same(i,i+N)){
            ans+=cnt[uf.root(i)];
        }else{
            int a=uf.root(i),b=uf.root(i+N);
            if(a>b)swap(a,b);
            ans+=cnt[a];
            ans+=cnt[b];
            
            ans-=cnt2[mp(a,b)];
        }
    }
    print(ans-N);
}