#1157474 (C++17) No.3517 Snake Kunekune Graph

• 問題: No.3517 Snake Kunekune Graph
• ユーザー: Yoyoyo8128
• 提出日時: 2026-04-16 12:54:34
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: RE
• 実行時間: -
• コード長: 4,368 bytes
• コンパイル時間: 2,596 ms
• コンパイル使用メモリ: 227,760 KB
• 実行使用メモリ: 20,992 KB
• 最終ジャッジ日時: 2026-04-24 20:54:38
• 合計ジャッジ時間: 17,356 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_1

ファイルパターン	結果
sample	WA * 1 RE * 1
other	WA * 11 RE * 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<int>>G(N);
    for(int i=0;i<M;i++){
        int u,v;
        cin>>u>>v;
        u--;v--;
        if(abs(A[u]-A[v])>X)continue;
        G[u].pb(v);
        G[v].pb(u);
    }
    for(int i=0;i<N;i++)sort(all(G[i]),[&A](int l,int r){return A[l]<A[r];});
    if(K==2){
        UnionFind uf(N);
        for(int i=0;i<N;i++){
            for(int e:G[i])uf.unite(i,e);
        }
        ll ans=0;
        for(int i=0;i<N;i++){
            if(uf.root(i)!=i)continue;
            ans+=uf.size(i)*uf.size(i)-1;
        }
        ans/=2;
        print(ans);
        exit(0);
    }
    assert(0);
}