提出詳細

提出id	提出時刻	ユーザー名	問題	言語	判定状況	判定	実行時間
114883	2023-10-24 10:11:12	euommo	J	cpp	11/11	AC	7

#include <bits/stdc++.h>

struct UnionFind {
  std::vector<int> e;
  UnionFind(int n) : e(n, -1) {}
  int find(int u) { return e[u] < 0 ? u : e[u] = find(e[u]); }
  void join(int u, int v) {
    u = find(u); v = find(v);
    if (u == v) return;
    if (e[u] > e[v]) std::swap(u, v);
    e[u] += e[v]; e[v] = u;
    return;
  }
};

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  //std::cin.exceptions(std::cin.failbit);

  int N, M, X, P;
  std::cin >> N >> M >> X >> P;

  std::vector<int> B(N+1), T(M+1);
  for (int i = 1; i <= N; ++i)
    std::cin >> B[i];
  for (int i = 1; i <= M; ++i)
    std::cin >> T[i];

  UnionFind uf(M+1);

  for (int u, v, i = 0; i < X; ++i) {
    std::cin >> u >> v;
    uf.join(u, v);
  }

  std::vector<int> need(M+1, 0);
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= M; ++j)
      if (B[i] - P <= T[j] and T[j] <= B[i] + P)
        need[uf.find(j)] = 1;
  }

  int ans = 0;
  for (int i = 1; i <= M; ++i)
    ans += need[i];
  std::cout << ans << '\n';

  return 0;
}

case1.txt AC 2
case2.txt AC 3
case3.txt AC 3
case4.txt AC 4
case5.txt AC 6
case6.txt AC 7
case9.txt AC 6
case10.txt AC 7
case11.txt AC 7
case13.txt AC 7
sample1.txt AC 6
7 AC7 AC