Submission #1234253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234253		hashdfdfh	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	7 ms	11080 KiB

bitaro

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

const int MAX_N = 200005;
const int B = 150; // Threshold for small/large Y_j

vector<int> graph[MAX_N]; // Original graph (u -> v)
vector<pair<int, int>> longestPaths[MAX_N]; // longestPaths[u]: top B paths (distance, node)
bool isForbidden[MAX_N]; // Marks forbidden nodes during queries
bool visited[MAX_N]; // Temporary marker for mergePaths

// Merges two path lists and keeps top B paths
vector<pair<int, int>> mergePaths(const vector<pair<int, int>>& pathsA, 
                                 const vector<pair<int, int>>& pathsB) {
    vector<pair<int, int>> merged;
    int i = 0, j = 0;
    
    while ((i < pathsA.size() || j < pathsB.size()) && merged.size() < B) {
        if (i == pathsA.size()) {
            if (!visited[pathsB[j].second]) {
                visited[pathsB[j].second] = true;
                merged.push_back(pathsB[j]);
            }
            j++;
            continue;
        }
        if (j == pathsB.size()) {
            if (!visited[pathsA[i].second]) {
                visited[pathsA[i].second] = true;
                merged.push_back({pathsA[i].first + 1, pathsA[i].second});
            }
            i++;
            continue;
        }
        if (pathsA[i].first + 1 > pathsB[j].first) {
            if (!visited[pathsA[i].second]) {
                visited[pathsA[i].second] = true;
                merged.push_back({pathsA[i].first + 1, pathsA[i].second});
            }
            i++;
        } else {
            if (!visited[pathsB[j].second]) {
                visited[pathsB[j].second] = true;
                merged.push_back(pathsB[j]);
            }
            j++;
        }
    }

    // Reset visited markers
    for (const auto& p : merged) visited[p.second] = false;
    return merged;
}

// Computes longest paths from all nodes to 'target' (skipping forbidden nodes)
int computeLongestPath(int target, const vector<int>& forbiddenNodes) {
    vector<int> maxDistance(MAX_N, -1);
    vector<bool> isAllowed(MAX_N, true);

    // Mark forbidden nodes
    for (int node : forbiddenNodes) isAllowed[node] = false;

    // Initialize DP
    maxDistance[target] = 0;

    // Process nodes in topological order (simplified)
    for (int u = 1; u < MAX_N; u++) {
        if (maxDistance[u] >= 0 && isAllowed[u]) {
            for (int v : graph[u]) {
                if (isAllowed[v]) {
                    maxDistance[v] = max(maxDistance[v], maxDistance[u] + 1);
                }
            }
        }
    }

    // Find maximum distance among allowed nodes
    int result = -1;
    for (int u = 1; u < MAX_N; u++) {
        if (isAllowed[u]) result = max(result, maxDistance[u]);
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, m, q;
    cin >> n >> m >> q;

    // Build graph
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }

    // Preprocess top B longest paths for each node
    for (int u = 1; u <= n; u++) {
        if (longestPaths[u].size() < B) {
            longestPaths[u].push_back({0, u});
        }
        for (int v : graph[u]) {
            longestPaths[v] = mergePaths(longestPaths[u], longestPaths[v]);
        }
    }

    // Process queries
    while (q--) {
        int target, k;
        cin >> target >> k;
        vector<int> forbiddenNodes(k);
        for (int i = 0; i < k; i++) cin >> forbiddenNodes[i];

        if (k >= B) {
            // Large Y_j: Compute longest path dynamically
            cout << computeLongestPath(target, forbiddenNodes) << "\n";
        } else {
            // Small Y_j: Use preprocessed paths
            for (int node : forbiddenNodes) isForbidden[node] = true;
            int maxDist = -1;
            for (const auto& p : longestPaths[target]) {
                if (!isForbidden[p.second]) {
                    maxDist = p.first;
                    break;
                }
            }
            for (int node : forbiddenNodes) isForbidden[node] = false;
            cout << maxDist << "\n";
        }
    }

    return 0;
}

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