Submission #426489

#	Time	Username	Problem	Language	Result	Execution time	Memory
426489		tengiz05	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	3 ms	460 KiB

bitaro

#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::vector<int>> e(n), p(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        e[u].push_back(v);
        p[v].push_back(u);
    }
    std::vector<bool> vis(n);
    std::vector<int> order;
    std::function<void(int)> dfs = [&](int u) {
        vis[u] = true;
        for (auto v : e[u]) {
            if (!vis[v]) {
                dfs(v);
            }
        }
        order.push_back(u);
    };
    dfs(0);
    std::reverse(order.begin(), order.end());
    while (q--) {
        int t, k;
        std::cin >> t >> k;
        t--;
        std::vector<int> dp(n);
        std::vector<bool> bad(n);
        for (int i = 0, x; i < k; i++) {
            std::cin >> x;
            bad[--x] = true;
            dp[x] = -1000000000;
        }
        for (auto u : order) {
            for (auto v : p[u]) {
                dp[u] = std::max(dp[u], dp[v] + 1);
            }
        }
        int ans = -1;
        std::vector<bool> vis(n);
        std::function<void(int)> dfs2 = [&](int u) {
            vis[u] = true;
            if (!bad[u]) {
                ans = std::max(ans, dp[t] - dp[u]);
            }
            for (auto v : p[u]) {
                if (!vis[v])
                    dfs2(v);
            }
        };
        dfs2(t);
        std::cout << std::max(-1, dp[t]) << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86