提出詳細

提出id	提出時刻	ユーザー名	問題	言語	判定状況	判定	実行時間
114885	2023-10-24 10:22:14	rk42745417	J	cpp	11/11	TLE	89

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>

signed main() {
    int n, m, x, p;
    std::cin >> n >> m >> x >> p;
    std::vector<int> b(n);
    std::vector<int> t(m);
    for (int &a : b)
        std::cin >> a;
    for (int &a : t)
        std::cin >> a;
    std::vector<bool> has(m);

    std::sort(b.begin(), b.end());
    std::vector<std::pair<int, int>> ki(m);
    for (int i = 0; i < m; i++) {
        ki[i].first = t[i];
        ki[i].second = i;
    }
    sort(ki.begin(), ki.end());
    int it = 0;
    for (int mise : b) {
        while (it < m && ki[it].first <= mise + p) {
            if (mise - p <= ki[it].first)
                has[ki[it].second] = true;
            it++;
        }
    }

    std::vector<std::vector<int>> edge(m);
    for (int i = 0, u, v; i < x; i++) {
        std::cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    std::vector<bool> vis(m);
    std::function<void(int)> dfs = [&] (int u) {
        vis[u] = true;
        for (int v : edge[u])
            if (!vis[v])
                dfs(v);
    };
    int ans = 0;
    for (int i = 0; i < m; i++)
        if (has[i] && !vis[i]) {
            dfs(i);
            ans++;
        }
    std::cout << ans << '\n';
}

case1.txt TLE 85
case2.txt TLE 87
case3.txt TLE 85
case4.txt TLE 86
case5.txt TLE 87
case6.txt TLE 88
case9.txt TLE 86
case10.txt AC 3
case11.txt TLE 89
case13.txt WA 10
sample1.txt AC 8
89 RE89 TLE