Submission #1234260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234260		hashdfdfh	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	10 ms	17480 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<int> reverseGraph[MAX_N]; // Reverse graph (v -> u)
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
int inDegree[MAX_N]; // In-degree for topological sort

// 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<int> tempInDegree(MAX_N, 0);
    queue<int> q;

    // Initialize in-degree and forbidden nodes
    for (int u = 1; u < MAX_N; u++) {
        tempInDegree[u] = inDegree[u];
        if (isForbidden[u]) maxDistance[u] = -1;
    }

    // Initialize DP: target node has distance 0
    maxDistance[target] = 0;

    // Topological sort with reverse graph
    for (int u = 1; u < MAX_N; u++) {
        if (tempInDegree[u] == 0 && !isForbidden[u]) {
            q.push(u);
        }
    }

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : reverseGraph[u]) {
            if (isForbidden[v]) continue;
            if (maxDistance[u] >= 0) {
                maxDistance[v] = max(maxDistance[v], maxDistance[u] + 1);
            }
            tempInDegree[v]--;
            if (tempInDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // Find maximum distance among allowed nodes
    int result = -1;
    for (int u = 1; u < MAX_N; u++) {
        if (!isForbidden[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 and reverse graph
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        reverseGraph[v].push_back(u);
        inDegree[v]++;
    }

    // Preprocess top B longest paths for each node (topological order)
    queue<int> topoQueue;
    for (int u = 1; u <= n; u++) {
        if (inDegree[u] == 0) topoQueue.push(u);
        longestPaths[u].push_back({0, u});
    }

    while (!topoQueue.empty()) {
        int u = topoQueue.front(); topoQueue.pop();
        for (int v : graph[u]) {
            longestPaths[v] = mergePaths(longestPaths[u], longestPaths[v]);
            inDegree[v]--;
            if (inDegree[v] == 0) topoQueue.push(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];
            isForbidden[forbiddenNodes[i]] = true;
        }

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

        // Reset forbidden markers
        for (int node : forbiddenNodes) isForbidden[node] = false;
    }

    return 0;
}

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