Submission #1326528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326528		johnadil	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	544 ms	261260 KiB

bitaro

#include <iostream>
#include <vector>

using namespace std;

const int BLOCK_SIZE = 320; 
const int INF = 1e9;

int main() {
    // Optimize standard I/O operations for performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, q;
    if (!(cin >> n >> m >> q)) return 0;

    vector<vector<int>> rev_adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        rev_adj[v].push_back(u);
    }

    vector<vector<pair<int, int>>> top_paths(n + 1);
    
    // Global seen array and a timer to check distinct origins in O(1)
    vector<int> seen(n + 1, 0);
    int timer = 0;

    // Optimized Precomputation phase using Two-Pointer Merge
    for (int v = 1; v <= n; v++) {
        // A node can always reach itself with distance 0
        top_paths[v].push_back({0, v});

        for (int u : rev_adj[v]) {
            timer++; // Unique token for this specific edge merge
            vector<pair<int, int>> merged;
            int i = 0, j = 0;
            int sz_v = top_paths[v].size();
            int sz_u = top_paths[u].size();

            // Merge two sorted arrays up to BLOCK_SIZE elements
            while (merged.size() < BLOCK_SIZE && (i < sz_v || j < sz_u)) {
                // Pick from top_paths[v] if top_paths[u] is exhausted, 
                // OR if top_paths[v]'s current distance is greater/equal.
                if (j == sz_u || (i < sz_v && top_paths[v][i].first >= top_paths[u][j].first + 1)) {
                    int origin = top_paths[v][i].second;
                    if (seen[origin] != timer) {
                        seen[origin] = timer;
                        merged.push_back(top_paths[v][i]);
                    }
                    i++;
                } else {
                    int origin = top_paths[u][j].second;
                    if (seen[origin] != timer) {
                        seen[origin] = timer;
                        merged.push_back({top_paths[u][j].first + 1, origin});
                    }
                    j++;
                }
            }
            // Update top_paths[v] with the newly merged top candidates
            top_paths[v] = merged;
        }
    }

    vector<int> dist(n + 1, -1);
    vector<bool> blocked(n + 1, false);

    // Query phase remains exactly the same
    for (int i = 0; i < q; i++) {
        int target, y_count;
        cin >> target >> y_count;

        vector<int> y(y_count);
        for (int j = 0; j < y_count; j++) {
            cin >> y[j];
            blocked[y[j]] = true;
        }

        if (y_count >= BLOCK_SIZE) {
            // Heavy Query: O(N + M) DP
            for (int v = 1; v <= target; v++) {
                dist[v] = blocked[v] ? -INF : 0;
                for (int u : rev_adj[v]) {
                    if (dist[u] != -INF) {
                        dist[v] = max(dist[v], dist[u] + 1);
                    }
                }
            }
            cout << (dist[target] < 0 ? -1 : dist[target]) << "\n";
        } else {
            // Light Query: O(B) Lookup
            int ans = -1;
            for (auto p : top_paths[target]) {
                if (!blocked[p.second]) {
                    ans = p.first;
                    break;
                }
            }
            cout << ans << "\n";
        }

        for (int j = 0; j < y_count; j++) {
            blocked[y[j]] = false;
        }
    }

    return 0;
}

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