Return to Question

#include <iostream>
#include <vector>

using namespace std;

int *value;
int *size;
int **valueC;
vector<int> *edges;
int k;

int length(int n);
int concat(const int &n1, const int &n2);
int dfs(int i, int reminder);

int length(int n) {
    int s = 0;
    do {
        n /= 10;
        s++;
    } while (n > 0);
    return s;
}

int concat(const int &n1, const int &n2) {
    int times = 1;
    while (times <= n2)
        times *= 10;
    return n1 * times + n2;
}


int dfs(int i, int reminder) {
    if (valueC[i][reminder] != -1)
        return valueC[i][reminder];
    int q = -1;
    for (int j : edges[i]) {
        int temp = -2;
        if (reminder - size[j] == 0)
            temp = value[j];
        else if (reminder - size[j] > 0)
            temp = dfs(j, reminder - size[j]);
        if (temp > q)
            q = temp;
    }
    if (q == -1)
        return valueC[i][reminder] = -2;
    else
        return valueC[i][reminder] = concat(value[i], q);
}

int main() {
    int n, m;
    cin >> n >> m >> k;
    value = new int[n + 1];
    size = new int[n + 1];
    valueC = new int *[n + 1];
    for (int i = 0; i < n + 1; ++i) {
        valueC[i] = new int[k];
        for (int j = 0; j < k; ++j) {
            valueC[i][j] = -1;
        }
    }
    for (int i = 1; i < n + 1; ++i) {
        cin >> value[i];
        size[i] = length(value[i]);
    }
    edges = new vector<int>[n + 1];
    for (int j = 0; j < m; ++j) {
        int s, e;
        cin >> s >> e;
        edges[s].push_back(e);
    }

    int maximum = 0;
    for (int i = 1; i < n + 1; ++i) {
        int temp = dfs(i, k - size[i]);
        if (temp > maximum)
            maximum = temp;
    }

    if (maximum != 0)
        cout << maximum;
    else
        cout << -1;
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int *value;
int *size;
int **valueC;
vector<int> *edges;
int k;

int length(int n);
int concat(const int &n1, const int &n2);
int dfs(int i, int reminder);

int length(int n) {
    int s = 0;
    do {
        n /= 10;
        s++;
    } while (n > 0);
    return s;
}

int concat(const int &n1, const int &n2) {
    int times = 1;
    while (times <= n2)
        times *= 10;
    return n1 * times + n2;
}


int dfs(int i, int reminder) {
    if (valueC[i][reminder] != -1)
        return valueC[i][reminder];
    int q = -1;
    for (int j : edges[i]) {
        int temp = -2;
        if (reminder - size[j] == 0)
            temp = value[j];
        else if (reminder - size[j] > 0)
            temp = dfs(j, reminder - size[j]);
        if (temp > q)
            q = temp;
    }
    if (q == -1)
        valueC[i][reminder] = -2;
    else
        valueC[i][reminder] = concat(value[i], q);
    return valueC[i][reminder];
}

int main() {
    int n, m;
    cin >> n >> m >> k;
    if (k == 0) {
        cout << -1;
        return 0;
    }
    value = new int[n];
    size = new int[n];
    valueC = new int *[n];
    for (int i = 0; i < n; ++i) {
        valueC[i] = new int[k];
        for (int j = 0; j < k; ++j) {
            valueC[i][j] = -1;
        }
    }
    for (int i = 0; i < n; ++i) {
        cin >> value[i];
        size[i] = length(value[i]);
    }
    edges = new vector<int>[n];
    for (int j = 0; j < m; ++j) {
        int s, e;
        cin >> s >> e;
        s--;
        e--;
        edges[s].push_back(e);
    }

    int maximum = 0;
    for (int i = 0; i < n; ++i) {
        int temp = dfs(i, k - size[i]);
        if (temp > maximum)
            maximum = temp;
    }

    if (maximum != 0)
        cout << maximum;
    else
        cout << -1;
    return 0;
}

Update 1

I remove one more space that is used as mentioned. about edges I use vector<int>[n] because I have n vertices and for each vertex I use a vector<int> to know that is connected to which vertices. about concat and length, I use int and I don't worry because the restriction on the question say that my numbers are at most 100000 and that is enough and both function work without overflow.

#include <iostream>
#include <vector>

using namespace std;

int *value;
int *size;
int **valueC;
vector<int> *edges;
int k;

int length(int n) {
    int s = 0;
    do {
        n /= 10;
        s++;
    } while (n > 0);
    return s;
}

int concat(const int &n1, const int &n2) {
    int times = 1;
    while (times <= n2)
        times *= 10;
    return n1 * times + n2;
}


int dfs(int i, int reminder) {
    if (valueC[i][reminder] != -1)
        return valueC[i][reminder];
    int q = -1;
    for (int j : edges[i]) {
        int temp = -2;
        if (reminder - size[j] == 0)
            temp = value[j];
        else if (reminder - size[j] > 0)
            temp = bfs(j, reminder - size[j]);
        if (temp > q)
            q = temp;
    }
    if (q == -1)
        return valueC[i][reminder] = -2;
    else
        return valueC[i][reminder] = concat(value[i], q);
}

int main() {
    int n, m;
    cin >> n >> m >> k;
    value = new int[n + 1];
    size = new int[n + 1];
    valueC = new int *[n + 1];
    for (int i = 0; i < n + 1; ++i) {
        valueC[i] = new int[k];
        for (int j = 0; j < k; ++j) {
            valueC[i][j] = -1;
        }
    }
    for (int i = 1; i < n + 1; ++i) {
        cin >> value[i];
        size[i] = length(value[i]);
    }
    edges = new vector<int>[n + 1];
    for (int j = 0; j < m; ++j) {
        int s, e;
        cin >> s >> e;
        edges[s].push_back(e);
    }

    int maximum = 0;
    for (int i = 1; i < n + 1; ++i) {
        int temp = bfs(i, k - size[i]);
        if (temp > maximum)
            maximum = temp;
    }

    if (maximum != 0)
        cout << maximum;
    else
        cout << -1;
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int *value;
int *size;
int **valueC;
vector<int> *edges;
int k;

int length(int n);
int concat(const int &n1, const int &n2);
int dfs(int i, int reminder);

int length(int n) {
    int s = 0;
    do {
        n /= 10;
        s++;
    } while (n > 0);
    return s;
}

int concat(const int &n1, const int &n2) {
    int times = 1;
    while (times <= n2)
        times *= 10;
    return n1 * times + n2;
}


int dfs(int i, int reminder) {
    if (valueC[i][reminder] != -1)
        return valueC[i][reminder];
    int q = -1;
    for (int j : edges[i]) {
        int temp = -2;
        if (reminder - size[j] == 0)
            temp = value[j];
        else if (reminder - size[j] > 0)
            temp = dfs(j, reminder - size[j]);
        if (temp > q)
            q = temp;
    }
    if (q == -1)
        return valueC[i][reminder] = -2;
    else
        return valueC[i][reminder] = concat(value[i], q);
}

int main() {
    int n, m;
    cin >> n >> m >> k;
    value = new int[n + 1];
    size = new int[n + 1];
    valueC = new int *[n + 1];
    for (int i = 0; i < n + 1; ++i) {
        valueC[i] = new int[k];
        for (int j = 0; j < k; ++j) {
            valueC[i][j] = -1;
        }
    }
    for (int i = 1; i < n + 1; ++i) {
        cin >> value[i];
        size[i] = length(value[i]);
    }
    edges = new vector<int>[n + 1];
    for (int j = 0; j < m; ++j) {
        int s, e;
        cin >> s >> e;
        edges[s].push_back(e);
    }

    int maximum = 0;
    for (int i = 1; i < n + 1; ++i) {
        int temp = dfs(i, k - size[i]);
        if (temp > maximum)
            maximum = temp;
    }

    if (maximum != 0)
        cout << maximum;
    else
        cout << -1;
    return 0;
}

There is a question in a contest but it doesn't have any answer. I solve it but I get time limit for most of test case. Is it possible to improve my code or give a better approach? Question:

My Solution: In my solution because we can traverse each edges and vertices more than one time, so I don't use something like visited array. I use deep first search to traverse all vertices and because we solve some problems more than one time, I use dynamic programming approach (to-down with memoization) to solve it faster however I get time limit. I Think my solution is right and I have time problem but maybe you find some implementation problem. (I hope that is true)

There is a question in a contest but it doesn't have any answer. I solve it but I get time limit for most of test case. Is it possible to improve my code or give a better approach?

Question

There is a directed graph with vertices \$1,...,n\$ and each vertex has a label which is \$a_i\$ (a number not character). we start walk and write label for each vertex we see in path (we can use vertices and edges more than one time) for example if we start from vertex \$v\$ and go to vertex \$u\$ then string of path is \$a_va_u\$. (if \$a_v=23\$ and \$a_u=456\$ then string of path is \$23456\$) we want to find strings of length \$k\$ and between different way of find that, choose one that produce maximum string of path (larger number) and print it.

Input

In the first line numbers n,m,k are given denoting the number of vertices, edges and length of string path that we want. Next line contains n integers one after another, i-th integer is equal to \$a_i\$​. (the number written on vertex i) Afterwards m lines each consisting of two integers u, v are given showing edge \$u \rightarrow v\$ exists in the graph.
\$1 \le v, u \le n\$
\$n, m, k \le 1000\$
\$1 \le a_i \le 100000\$
the graph can contain loop or multiple edges.

Output

In the only line of output display the k digit number that is maximized. Display −1 if no answer exists!

Sample input

5 4 3
4 12 3 1 1
1 2
2 3
1 4
4 5

Sample output

412

My Solution

In my solution because we can traverse each edges and vertices more than one time, so I don't use something like visited array. I use deep first search to traverse all vertices and because we solve some problems more than one time, I use dynamic programming approach (to-down with memoization) to solve it faster however I get time limit. I Think my solution is right and I have time problem but maybe you find some implementation problem. (I hope that is true)