Submission #1272604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272604		veljko	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	2096 ms	13660 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, Q;
    if (!(cin >> N >> M >> Q)) return 0;

    vector<vector<int>> g(N), gr(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b;
        --a; --b; // convert to 0-based
        g[a].push_back(b);    // edge a -> b (from higher to lower town index)
        gr[b].push_back(a);   // reverse edge b <- a
    }

    // We'll use timestamp technique for per-query marking to avoid clearing large arrays.
    vector<int> mark_reach(N, 0);
    vector<int> mark_block(N, 0);
    int cur_mark = 1;

    vector<int> qqueue;
    vector<int> nodes_in_R; nodes_in_R.reserve(N);
    vector<int> dp(N, INT_MIN);

    for (int qi = 0; qi < Q; ++qi, ++cur_mark) {
        int T, Y;
        cin >> T >> Y;
        --T;

        // read blocked list, mark them (timestamped)
        for (int i = 0; i < Y; ++i) {
            int x; cin >> x; --x;
            mark_block[x] = cur_mark;
        }

        // 1) reverse BFS/DFS from T to find all nodes that can reach T
        qqueue.clear();
        nodes_in_R.clear();

        // BFS using vector as queue
        int head = 0;
        qqueue.push_back(T);
        mark_reach[T] = cur_mark;

        while (head < (int)qqueue.size()) {
            int u = qqueue[head++];
            nodes_in_R.push_back(u);
            for (int p : gr[u]) {
                if (mark_reach[p] != cur_mark) {
                    mark_reach[p] = cur_mark;
                    qqueue.push_back(p);
                }
            }
        }

        if (nodes_in_R.empty()) {
            // only possible if graph empty and T isolated; but nodes_in_R contains T always
            cout << -1 << '\n';
            continue;
        }

        // 2) Process nodes in decreasing index order (valid topological order because edges go from smaller->larger index)
        //    but we should process nodes_in_R sorted descending to be safe.
        sort(nodes_in_R.begin(), nodes_in_R.end(), greater<int>());

        // initialize dp for nodes in R
        for (int u : nodes_in_R) dp[u] = INT_MIN;
        dp[T] = 0;

        for (int u : nodes_in_R) {
            if (u == T) continue;
            int best = INT_MIN;
            // u -> v; we only consider v that are in R (mark_reach == cur_mark)
            for (int v : g[u]) {
                if (mark_reach[v] == cur_mark && dp[v] != INT_MIN) {
                    best = max(best, dp[v] + 1);
                }
            }
            dp[u] = best;
        }

        // 3) find maximum among unblocked nodes in R that can reach T (dp[u] != INT_MIN)
        int ans = INT_MIN;
        for (int u : nodes_in_R) {
            if (dp[u] == INT_MIN) continue;           // cannot reach T
            if (mark_block[u] == cur_mark) continue;  // busy friend, skip as a source
            ans = max(ans, dp[u]);
        }

        if (ans == INT_MIN) cout << -1 << '\n';
        else cout << ans << '\n';
    }

    return 0;
}

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