提出詳細

提出id	提出時刻	ユーザー名	問題	言語	判定状況	判定	実行時間
114886	2023-10-24 10:23:47	rk42745417	J	cpp	11/11	TLE	88

#include <queue>
#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::queue<int> bfs;
    int ans = 0;
    for (int i = 0; i < m; i++)
        if (has[i] && !vis[i]) {
            bfs.push(i);
            while (!bfs.empty()) {
                int u = bfs.front();
                vis[u] = true;
                bfs.pop();
                for (int v : edge[u])
                    if (!vis[v])
                        bfs.push(v);
            }
            ans++;
        }
    std::cout << ans << '\n';
}

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