Submission #1313738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313738		orzorzorz	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2110 ms	331480 KiB

bitaro

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

const int mxN = 1e5 + 5;
const int B = 320; // Block size ~ sqrt(N)

vector<int> adj[mxN]; // Forward edges
// Stores {distance, source_id}
vector<pair<int, int>> best[mxN]; 

// For large queries
int dp_dist[mxN]; 

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m, q;
    cin >> n >> m >> q;
    
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
    }

    // --- Part 1: Precomputation (Small Y) ---
    // Iterate in topological order (0 to n-1 is guaranteed by Si < Ei)
    for(int i = 0; i < n; i++) {
        // 1. Add self as a valid starting point
        best[i].push_back({0, i});
        
        // 2. Sort to find longest paths. 
        // Note: best[i] contains entries pushed from predecessors + self.
        sort(best[i].rbegin(), best[i].rend());
        
        // 3. Keep only top B unique sources
        vector<pair<int, int>> unique_best;
        // Simple check for duplicates is fast enough for small B
        // Using a "seen" array is faster but requires reset. 
        // Since B is small, linear scan is fine.
        for(auto &p : best[i]) {
            if(unique_best.size() >= B) break;
            
            bool dup = false;
            for(auto &existing : unique_best) {
                if(existing.second == p.second) {
                    dup = true;
                    break;
                }
            }
            if(!dup) unique_best.push_back(p);
        }
        best[i] = unique_best;

        // 4. Propagate to neighbors
        for(int v : adj[i]) {
            for(auto &p : best[i]) {
                // Push path extended by 1
                best[v].push_back({p.first + 1, p.second});
            }
        }
    }

    // --- Part 2: Queries ---
    while(q--) {
        int t, y;
        cin >> t >> y;
        --t;
        
        vector<int> busy_nodes(y);
        for(int i = 0; i < y; i++) {
            cin >> busy_nodes[i];
            --busy_nodes[i];
        }

        if(y < B) {
            // fast query using precalc
            int ans = -1;
            for(auto &p : best[t]) {
                // p is {distance, source_id}
                bool is_busy = false;
                for(int b : busy_nodes) {
                    if(b == p.second) {
                        is_busy = true;
                        break;
                    }
                }
                if(!is_busy) {
                    ans = p.first;
                    break;
                }
            }
            cout << ans << "\n";
        } else {
            // heavy query: DP on graph
            // Use a bool array or set for O(1) busy check
            // Since we loop 0..N, we can mark array
            for(int i = 0; i < n; i++) dp_dist[i] = -1e9; // Init to -inf
            
            // Mark busy nodes temporarily
            // Actually, standard DP approach:
            // dp[i] = max length of valid path ending at i
            // Base case: if i is NOT busy, it can start a path (len 0)
            
            // Optimization: Only need to process nodes <= t because i < j
            
            // We need a fast lookup for busy nodes
            vector<bool> is_busy(n, false);
            for(int b : busy_nodes) is_busy[b] = true;
            
            for(int i = 0; i <= t; i++) {
                // If i is a valid start, path len is at least 0
                if(!is_busy[i]) {
                    dp_dist[i] = max(dp_dist[i], 0);
                }
                
                // If valid path reaches i, propagate to neighbors
                if(dp_dist[i] >= 0) {
                     for(int v : adj[i]) {
                         // Only need to propagate if v <= t (optimization)
                         if(v <= t) {
                             dp_dist[v] = max(dp_dist[v], dp_dist[i] + 1);
                         }
                     }
                }
            }
            
            cout << (dp_dist[t] < 0 ? -1 : dp_dist[t]) << "\n";
        }
    }

    return 0;
}

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