提出詳細

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

#pragma GCC optimize("Ofast")
#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), T(M+1);
  for (int i = 0; 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::sort(B.begin(), B.end());
  std::vector<int> ord(M);
  std::iota(ord.begin(), ord.end(), 1);
  std::sort(ord.begin(), ord.end(), [&](int a, int b) { return T[a] < T[b]; });

  std::vector<int> cnt(M+1, 0);
  for (int i = 0, j = 0; j < M; ++j) {
    while (i < N and B[i] - P <= T[ord[j]]) ++i;
    cnt[ord[j]] += i;
  }
  for (int i = 0, j = 0; j < M; ++j) {
    while (i < N and B[i] + P < T[ord[j]]) ++i;
    cnt[ord[j]] -= i;
  }

  std::vector<int> need(M+1, 0);
  for (int i = 1; i <= M; ++i)
    if (cnt[i] > 0) need[uf.find(i)] = 1;

  std::cout << std::accumulate(need.begin(), need.end(), 0) << '\n';

  return 0;
}

case1.txt AC 2
case2.txt TLE 86
case3.txt TLE 85
case4.txt TLE 85
case5.txt TLE 85
case6.txt TLE 85
case9.txt TLE 85
case10.txt TLE 85
case11.txt TLE 87
case13.txt TLE 85
sample1.txt AC 2
87 RE87 TLE