提出詳細

提出id	提出時刻	ユーザー名	問題	言語	判定状況	判定	実行時間
114874	2023-10-24 09:35:30	euommo	J	cpp	11/11	TLE	88

#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::set<std::pair<int, int>> s;
  for (int i = 1; i <= M; ++i)
    s.emplace(T[i], uf.find(i));

  std::vector<int> need(M+1);
  for (int i = 1; i <= N; ++i) {
    int lb = B[i] - P, rb = B[i] + P;
    auto it = s.lower_bound(std::make_pair(lb, -1));
    while (it != s.end() and it->first <= rb) {
      need[it->second] = 1;
      it = s.erase(it);
    }
  }

  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 TLE 86
case3.txt TLE 88
case4.txt TLE 85
case5.txt TLE 85
case6.txt TLE 85
case9.txt TLE 85
case10.txt TLE 85
case11.txt TLE 85
case13.txt TLE 85
sample1.txt AC 2
88 RE88 TLE