#1161647 (C++23) No.3517 Snake Kunekune Graph

• 問題: No.3517 Snake Kunekune Graph
• ユーザー: tassei903
• 提出日時: 2026-04-25 18:17:51
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 3,158 bytes
• コンパイル時間: 3,790 ms
• コンパイル使用メモリ: 342,128 KB
• 実行使用メモリ: 33,920 KB
• 最終ジャッジ日時: 2026-04-25 18:18:11
• 合計ジャッジ時間: 11,573 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for(ll i = (a)-1; i >= (b); i--)
#define fore(e, v) for(auto&& e : v)
#define all(a) begin(a), end(a)
#define sz(a) (int)(a.size())
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

template<typename T, typename S> bool chmin(T& a, const S& b) { return a > b ? a = b, 1 : 0; }
template<typename T, typename S> bool chmax(T& a, const S& b) { return a < b ? a = b, 1 : 0; }
 
const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;
 
#define i128 __int128_t
 
struct _ {
   _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }
} __;

void debug(auto ...vs) {
    ((cerr << vs << " "), ...) << endl;
}
ll extgcd(ll a, ll b, ll& x, ll& y) {
   // assert(a >= 0 && b >= 0);
   if(!b) return x = 1, y = 0, a;
   ll d = extgcd(b, a % b, y, x);
   y -= a / b * x;
   return d;
}
ll inv_mod(ll x, ll md) {
   ll y, z;
   extgcd(x, md, y, z);
   return (y % md + md) % md;
}

struct DSU {
	int n;
	vi par;

	DSU(int n) : n(n), par(n, -1) {} 

	int leader(int x) {
		if (par[x] < 0) return x;
		return par[x] = leader(par[x]);
	}

	bool same(int x, int y) {
		return leader(x) == leader(y);
	}

	void merge(int x, int y) {
		x = leader(x);
		y = leader(y);
		if (x == y) return;
		if (par[x] > par[y]) {
			swap(x, y);
		}
		par[x] += par[y];
		par[y] = x;
	}
};

void solve() {
	int n, m, x, k;cin >> n >> m >> x >> k;
	vi a(n);
	rep(i, n) cin >> a[i];
	vector<vi> g(n);
	rep(m) {
		int u, v;cin >> u >> v;
		u--,v--;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}	
	
	if (k == 2) {
		DSU dsu(n);
		rep(i, n) for(auto j: g[i]) {
			if (abs(a[i] - a[j]) <= x) {
				dsu.merge(i, j);
			}
		}
		ll ans = 0;
		rep(i, n) {
			if (dsu.leader(i) != i) continue;
			ll s = -dsu.par[i];
			ans += s * (s - 1);
		}
		cout << ans << endl;
	}
	else {
		DSU dsu(n * 2);
		ll ans = 0;
		rep(i, n) for(auto j: g[i]) {
			if (abs(a[j] - a[i]) > x) continue;
			if (a[i] <= a[j]) {
				dsu.merge(i, j + n);
			}
			else {
				dsu.merge(i + n, j);
			}
		}

		rep(i, n) {
			int r = INF, l = -INF;
			fore(j, g[i]) {
				if (a[j] >= a[i]) {
					chmin(r, a[j]);
				}
				else {
					chmax(l, a[j]);
				}
			}
			if (r - l <= x) dsu.merge(i, i + n);
		}

		vector<vi> f(n * 2);
		rep(i, n * 2) {
			f[dsu.leader(i)].emplace_back(i);
		}
		vi seen(n * 2);
		rep(i, n * 2) {
			if (i != dsu.leader(i)) continue;
			int cnt = 0;
			for (auto x: f[i]) {
				if (x >= n) {
					x-=n;
				}
				if (seen[x]==0) {
					seen[x] = 1;
					cnt++;
				}
			}
			ans += (ll) cnt * (cnt - 1);

			for (auto x: f[i]) {
				if (x >= n) {
					x-=n;
				}
				seen[x] = 0;
			}
		}
		cout << ans << endl;
	}
}

int main(){
    int T = 1;
    // int T;cin >> T;
    while(T--) {

        solve();
    }
    
}