CSES - Aalto Competitive Programming 2024 - wk6 - Mon - Results
Submission details
Task:Terrible security
Sender:arnxxau
Submission time:2024-10-07 16:42:57 +0300
Language:C++ (C++11)
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'void dfs(int, std::vector<std::vector<int> >, int*, bool*)':
input/code.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < adj[node].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~
input/code.cpp: In function 'int findLongestPath(std::vector<std::vector<int> >, int)':
input/code.cpp:31:5: error: 'memset' was not declared in this scope
   31 |     memset(dp, 0, sizeof dp);
      |     ^~~~~~
input/code.cpp:6:1: note: 'memset' is defined in header '<cstring>'; did you forget to '#include <cstring>'?
    5 | #include <queue>
  +++ |+#include <cstring>
    6 | #include <vector>
input/code.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i = 1; i <= adj.size();...

Code

// C++ program to find the longest
// path in the DAG

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// Function to traverse the DAG
// and apply Dynamic Programming
// to find the longest path
void dfs(int node, vector<vector<int>> adj, int dp[], bool vis[]) {
    // Mark as visited
    vis[node] = true;

    // Traverse for all its children
    for (int i = 0; i < adj[node].size(); i++) {
        // If not visited
        if (!vis[adj[node][i]])
            dfs(adj[node][i], adj, dp, vis);

        // Store the max of the paths
        dp[node] = max(dp[node], 1 + dp[adj[node][i]]);
    }
}

// Function that returns the longest path
int findLongestPath(vector<vector<int>> adj, int k) {
    // Dp array
    int dp[adj.size() + 1];
    memset(dp, 0, sizeof dp);

    // Visited array to know if the node
    // has been visited previously or not
    bool vis[adj.size() + 1];
    memset(vis, false, sizeof vis);

    dfs(k, adj, dp, vis);


    int ans = 0;

    // Traverse and find the maximum of all dp[i]
    for (int i = 1; i <= adj.size(); i++) {
        ans = max(ans, dp[i]);
    }
    return ans;
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<vector<int>> adj(n + 1);

    for (int i = 1; i <= n; ++i) {
        int b;
        cin >> b;
        adj[i].push_back(b);
    }

    for (int i = 0; i < q; i++) {
        int k;
        cin >> k;
        cout << findLongestPath(adj, k) << ' ';
    }
    cout << endl;
    return 0;
}