提出 #70485357

---

ソースコード 拡げる

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = std::forward<U>(y), true); }

template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = std::forward<U>(y), true); }

template <class T> void mkuni(std::vector<T>& v) {
    std::ranges::sort(v);
    auto result = std::ranges::unique(v);
    v.erase(result.begin(), result.end());
}

template <class T> int lwb(const std::vector<T>& v, const T& x) {
    return std::distance(v.begin(), std::ranges::lower_bound(v, x));
}

using namespace std;

using ll = long long;

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> x(M), y(M);
    for (int i = 0; i < M; i++) {
        cin >> x[i] >> y[i];
        x[i]--, y[i]--;
    }
    vector<int> P(N);
    for (int i = 0; i < N; i++) {
        cin >> P[i];
        P[i]--;
    }

    for (int i = 0; i < M; i++) {
        x[i] = P[x[i]];
        y[i] = P[y[i]];
    }
    vector<vector<int>> G(N);
    vector<int> indeg(N, 0), pre(N, -2);
    for (int i = 0; i < M; i++) {
        G[x[i]].emplace_back(y[i]);
        chmax(pre[y[i]], x[i]);
        indeg[y[i]]++;
    }
    priority_queue<int> pq;
    for (int i = 0; i < N; i++) {
        if (indeg[i] == 0) {
            pq.emplace(i);
        }
    }
    vector<bool> used(N, false);
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (not used[i]) {
            while (int(pq.size()) > 1) {
                int u = pq.top();
                pq.pop();
                ans++;
                used[u] = true;
            }
            assert(pq.top() == i);
            pq.pop();
        }
        for (int j : G[i]) {
            if (--indeg[j] == 0) {
                pq.emplace(j);
            }
        }
    }

    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int T;
    cin >> T;
    for (; T--;) {
        solve();
    }
    return 0;
}

提出情報

ジャッジ結果