結果

問題 No.3517 Snake Kunekune Graph
コンテスト
ユーザー Kude
提出日時 2026-04-25 01:44:48
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,468 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,665 ms
コンパイル使用メモリ 366,784 KB
実行使用メモリ 27,232 KB
最終ジャッジ日時 2026-04-25 01:45:18
合計ジャッジ時間 28,790 ms
ジャッジサーバーID
（参考情報） 		judge4_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 43 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC target("popcnt")
#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, x, k;
  cin >> n >> m >> x >> k;
  VI a(n);
  rep(i, n) cin >> a[i];
  if (k == 2) {
    dsu uf(n);
    rep(_, m) {
      int u, v;
      cin >> u >> v;
      u--, v--;
      if (abs(a[u] - a[v]) <= x) uf.merge(u, v);
    }
    ll ans = 0;
    rep(v, n) if (uf.leader(v) == v) {
      int sz = uf.size(v);
      ans += sz * ll(sz - 1);
    }
    cout << ans << '\n';
    return 0;
  }
  VI ex;
  VVI g(n);
  int sz = 0;
  rep(_, m) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    if (abs(a[u] - a[v]) > x) continue;
    g[u].emplace_back(sz);
    g[v].emplace_back(sz);
    ex.emplace_back(u ^ v);
    sz++;
  }
  dsu uf(sz);
  rep(u, n) {
    ranges::sort(g[u], {}, [&](int i) { return a[ex[i]^u]; });
    rep(p, ssize(g[u]) - 1) {
      int i = g[u][p], j = g[u][p+1];
      int vi = u ^ ex[i], vj = u ^ ex[j];
      if (max({a[u], a[vi], a[vj]}) - min({a[u], a[vi], a[vj]}) <= x) {
        uf.merge(i, j);
      }
    }
  }
  auto gs = uf.groups();
  VI eid2gid(sz);
  rep(g, ssize(gs)) for (int i : gs[g]) eid2gid[i] = g;
  VVI gid2vs(ssize(gs));
  rep(v, n) for (int i : g[v]) gid2vs[eid2gid[i]].emplace_back(v);
  for (auto& vs : gid2vs) vs.erase(unique(all(vs)), vs.end());
  ll ans = 0;
  for (int s = 0; s < n;) {
    using ull = unsigned long long;
    static vector<ull> dp1, dp2;
    dp1.assign(gs.size(), 0);
    dp2.assign(n, 0);
    rep(h, 64) {
      if (s == n) break;
      dp2[s] |= 1ULL << h;
      for (int i : g[s]) dp1[eid2gid[i]] |= 1ULL << h;
      s++;
    }
    rep(g, ssize(gs)) for (int v : gid2vs[g]) dp2[v] |= dp1[g];
    rep(v, n) ans += popcount(dp2[v]);
  }
  ans -= n;
  cout << ans << '\n';
}
0