Submission #1234261

#TimeUsernameProblemLanguageResultExecution timeMemory
1234261hashdfdfhBitaro’s Party (JOI18_bitaro)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long lonng

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;
}

signed 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;
}

Compilation message (stderr)

bitaro.cpp:5:11: error: expected initializer before 'MAX_N'
    5 | const int MAX_N = 200005;
      |           ^~~~~
bitaro.cpp:6:11: error: expected initializer before 'B'
    6 | const int B = 150; // Threshold for small/large Y_j
      |           ^
bitaro.cpp:8:11: error: template argument 1 is invalid
    8 | vector<int> graph[MAX_N]; // Original graph (u -> v)
      |           ^
bitaro.cpp:8:11: error: template argument 2 is invalid
bitaro.cpp:8:19: error: 'MAX_N' was not declared in this scope
    8 | vector<int> graph[MAX_N]; // Original graph (u -> v)
      |                   ^~~~~
bitaro.cpp:9:11: error: template argument 1 is invalid
    9 | vector<int> reverseGraph[MAX_N]; // Reverse graph (v -> u)
      |           ^
bitaro.cpp:9:11: error: template argument 2 is invalid
bitaro.cpp:9:26: error: 'MAX_N' was not declared in this scope
    9 | vector<int> reverseGraph[MAX_N]; // Reverse graph (v -> u)
      |                          ^~~~~
bitaro.cpp:10:21: error: wrong number of template arguments (1, should be 2)
   10 | vector<pair<int, int>> longestPaths[MAX_N]; // longestPaths[u]: top B paths (distance, node)
      |                     ^~
In file included from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from bitaro.cpp:1:
/usr/include/c++/11/bits/stl_pair.h:211:12: note: provided for 'template<class _T1, class _T2> struct std::pair'
  211 |     struct pair
      |            ^~~~
bitaro.cpp:10:42: error: template argument 1 is invalid
   10 | vector<pair<int, int>> longestPaths[MAX_N]; // longestPaths[u]: top B paths (distance, node)
      |                                          ^
bitaro.cpp:10:42: error: template argument 2 is invalid
bitaro.cpp:11:18: error: 'MAX_N' was not declared in this scope
   11 | bool isForbidden[MAX_N]; // Marks forbidden nodes during queries
      |                  ^~~~~
bitaro.cpp:12:14: error: 'MAX_N' was not declared in this scope
   12 | bool visited[MAX_N]; // Temporary marker for mergePaths
      |              ^~~~~
bitaro.cpp:13:5: error: expected initializer before 'inDegree'
   13 | int inDegree[MAX_N]; // In-degree for topological sort
      |     ^~~~~~~~
bitaro.cpp:16:21: error: wrong number of template arguments (1, should be 2)
   16 | vector<pair<int, int>> mergePaths(const vector<pair<int, int>>& pathsA,
      |                     ^~
In file included from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from bitaro.cpp:1:
/usr/include/c++/11/bits/stl_pair.h:211:12: note: provided for 'template<class _T1, class _T2> struct std::pair'
  211 |     struct pair
      |            ^~~~
bitaro.cpp:17:70: error: template argument 1 is invalid
   17 |                                  const vector<pair<int, int>>& pathsB) {
      |                                                                      ^
bitaro.cpp:17:70: error: template argument 2 is invalid
bitaro.cpp:17:72: error: expected unqualified-id before '{' token
   17 |                                  const vector<pair<int, int>>& pathsB) {
      |                                                                        ^
bitaro.cpp:59:5: error: expected initializer before 'computeLongestPath'
   59 | int computeLongestPath(int target, const vector<int>& forbiddenNodes) {
      |     ^~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:106:9: error: expected initializer before 'n'
  106 |     int n, m, q;
      |         ^
bitaro.cpp:107:12: error: 'n' was not declared in this scope; did you mean 'yn'?
  107 |     cin >> n >> m >> q;
      |            ^
      |            yn
bitaro.cpp:107:17: error: 'm' was not declared in this scope; did you mean 'tm'?
  107 |     cin >> n >> m >> q;
      |                 ^
      |                 tm
bitaro.cpp:107:22: error: 'q' was not declared in this scope
  107 |     cin >> n >> m >> q;
      |                      ^
bitaro.cpp:110:14: error: expected ';' before 'i'
  110 |     for (int i = 1; i <= m; i++) {
      |              ^
bitaro.cpp:110:14: error: 'i' was not declared in this scope
bitaro.cpp:110:27: error: expected ')' before ';' token
  110 |     for (int i = 1; i <= m; i++) {
      |         ~                 ^
      |                           )
bitaro.cpp:110:29: error: 'i' was not declared in this scope
  110 |     for (int i = 1; i <= m; i++) {
      |                             ^
bitaro.cpp:119:14: error: template argument 1 is invalid
  119 |     queue<int> topoQueue;
      |              ^
bitaro.cpp:119:14: error: template argument 2 is invalid
bitaro.cpp:120:14: error: expected ';' before 'u'
  120 |     for (int u = 1; u <= n; u++) {
      |              ^
bitaro.cpp:120:14: error: 'u' was not declared in this scope
bitaro.cpp:120:27: error: expected ')' before ';' token
  120 |     for (int u = 1; u <= n; u++) {
      |         ~                 ^
      |                           )
bitaro.cpp:120:29: error: 'u' was not declared in this scope
  120 |     for (int u = 1; u <= n; u++) {
      |                             ^
bitaro.cpp:125:23: error: request for member 'empty' in 'topoQueue', which is of non-class type 'int'
  125 |     while (!topoQueue.empty()) {
      |                       ^~~~~
bitaro.cpp:126:13: error: expected initializer before 'u'
  126 |         int u = topoQueue.front(); topoQueue.pop();
      |             ^
bitaro.cpp:126:46: error: request for member 'pop' in 'topoQueue', which is of non-class type 'int'
  126 |         int u = topoQueue.front(); topoQueue.pop();
      |                                              ^~~
bitaro.cpp:127:18: error: expected ';' before 'v'
  127 |         for (int v : graph[u]) {
      |                  ^
bitaro.cpp:127:20: error: found ':' in nested-name-specifier, expected '::'
  127 |         for (int v : graph[u]) {
      |                    ^
      |                    ::
bitaro.cpp:127:18: error: 'v' has not been declared
  127 |         for (int v : graph[u]) {
      |                  ^
bitaro.cpp:127:30: error: expected ';' before ')' token
  127 |         for (int v : graph[u]) {
      |                              ^
      |                              ;
bitaro.cpp:128:13: error: 'longestPaths' was not declared in this scope
  128 |             longestPaths[v] = mergePaths(longestPaths[u], longestPaths[v]);
      |             ^~~~~~~~~~~~
bitaro.cpp:128:26: error: 'v' was not declared in this scope
  128 |             longestPaths[v] = mergePaths(longestPaths[u], longestPaths[v]);
      |                          ^
bitaro.cpp:128:31: error: 'mergePaths' was not declared in this scope
  128 |             longestPaths[v] = mergePaths(longestPaths[u], longestPaths[v]);
      |                               ^~~~~~~~~~
bitaro.cpp:129:13: error: 'inDegree' was not declared in this scope
  129 |             inDegree[v]--;
      |             ^~~~~~~~
bitaro.cpp:130:45: error: request for member 'push' in 'topoQueue', which is of non-class type 'int'
  130 |             if (inDegree[v] == 0) topoQueue.push(v);
      |                                             ^~~~
bitaro.cpp:136:13: error: expected initializer before 'target'
  136 |         int target, k;
      |             ^~~~~~
bitaro.cpp:137:16: error: 'target' was not declared in this scope
  137 |         cin >> target >> k;
      |                ^~~~~~
bitaro.cpp:137:26: error: 'k' was not declared in this scope
  137 |         cin >> target >> k;
      |                          ^
bitaro.cpp:138:19: error: template argument 1 is invalid
  138 |         vector<int> forbiddenNodes(k);
      |                   ^
bitaro.cpp:138:19: error: template argument 2 is invalid
bitaro.cpp:139:18: error: expected ';' before 'i'
  139 |         for (int i = 0; i < k; i++) {
      |                  ^
bitaro.cpp:139:30: error: expected ')' before ';' token
  139 |         for (int i = 0; i < k; i++) {
      |             ~                ^
      |                              )
bitaro.cpp:144:18: error: 'B' was not declared in this scope
  144 |         if (k >= B) {
      |                  ^
bitaro.cpp:146:21: error: 'computeLongestPath' was not declared in this scope
  146 |             cout << computeLongestPath(target, forbiddenNodes) << "\n";
      |                     ^~~~~~~~~~~~~~~~~~
bitaro.cpp:149:17: error: expected initializer before 'maxDist'
  149 |             int maxDist = -1;
      |                 ^~~~~~~
bitaro.cpp:150:34: error: 'longestPaths' was not declared in this scope
  150 |             for (const auto& p : longestPaths[target]) {
      |                                  ^~~~~~~~~~~~
bitaro.cpp:151:22: error: 'isForbidden' was not declared in this scope
  151 |                 if (!isForbidden[p.second]) {
      |                      ^~~~~~~~~~~
bitaro.cpp:152:21: error: 'maxDist' was not declared in this scope
  152 |                     maxDist = p.first;
      |                     ^~~~~~~
bitaro.cpp:156:21: error: 'maxDist' was not declared in this scope
  156 |             cout << maxDist << "\n";
      |                     ^~~~~~~
bitaro.cpp:160:18: error: expected ';' before 'node'
  160 |         for (int node : forbiddenNodes) isForbidden[node] = false;
      |                  ^~~~
bitaro.cpp:160:23: error: found ':' in nested-name-specifier, expected '::'
  160 |         for (int node : forbiddenNodes) isForbidden[node] = false;
      |                       ^
      |                       ::
bitaro.cpp:160:18: error: 'node' has not been declared
  160 |         for (int node : forbiddenNodes) isForbidden[node] = false;
      |                  ^~~~
bitaro.cpp:160:39: error: expected ';' before ')' token
  160 |         for (int node : forbiddenNodes) isForbidden[node] = false;
      |                                       ^
      |                                       ;
bitaro.cpp:160:41: error: 'isForbidden' was not declared in this scope
  160 |         for (int node : forbiddenNodes) isForbidden[node] = false;
      |                                         ^~~~~~~~~~~
bitaro.cpp:160:53: error: 'node' was not declared in this scope
  160 |         for (int node : forbiddenNodes) isForbidden[node] = false;
      |                                                     ^~~~