Submission #1326527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326527		johnadil	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2094 ms	5860 KiB

bitaro

#include <iostream>
#include <vector>
#include <algorithm>

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;

    // We store the reverse graph to look back at incoming edges
    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);
    }

    // top_paths[v] stores up to BLOCK_SIZE pairs of {distance, origin_node}
    vector<vector<pair<int, int>>> top_paths(n + 1);
    
    // used_time array replaces a boolean visited array to avoid O(N) resets
    vector<int> used_time(n + 1, 0);
    int current_time = 0;

    // Precomputation phase
    for (int v = 1; v <= n; v++) {
        current_time++;
        vector<pair<int, int>> candidates;
        
        // A node can always reach itself with a distance of 0
        candidates.push_back({0, v});
        
        // Gather all precomputed paths from incoming edges
        for (int u : rev_adj[v]) {
            for (auto p : top_paths[u]) {
                candidates.push_back({p.first + 1, p.second});
            }
        }

        // Sort candidates by distance in descending order
        sort(candidates.rbegin(), candidates.rend());

        // Greedily pick the top distinct origins up to the BLOCK_SIZE limit
        for (auto p : candidates) {
            if (used_time[p.second] != current_time) {
                used_time[p.second] = current_time;
                top_paths[v].push_back(p);
                
                if (top_paths[v].size() == BLOCK_SIZE) {
                    break;
                }
            }
        }
    }

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

    // Query phase
    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: Standard DAG Longest Path 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: Fast lookup from precomputed top paths
            int ans = -1;
            for (auto p : top_paths[target]) {
                if (!blocked[p.second]) {
                    ans = p.first;
                    break;
                }
            }
            cout << ans << "\n";
        }

        // Reset the blocked array efficiently
        for (int j = 0; j < y_count; j++) {
            blocked[y[j]] = false;
        }
    }

    return 0;
}

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