https://codility.com/programmers/challenges/magnesium2014

longestAscendingPath.cpp

#include <vector>
#include <algorithm>
using namespace std;
 
struct Road {
    int start;
    int end;
    int val;
};
 
bool cmp(const Road &a, const Road &b) {
    return a.val < b.val;
}
 
int solution(int N, vector<int> &A, vector<int> &B, vector<int> &C) {
    int M = A.size();
    vector<Road> roads(M);
    for (int i = 0; i < M; i++) {
        roads[i].start = A[i];
        roads[i].end = B[i];
        roads[i].val = C[i];
    }
    sort(roads.begin(), roads.end(), cmp);
    vector<pair<int, int>> dp(N); // first: the longest length ends with this node; second: the last path val to this node;
    int result = 0;
    for (int i = 0; i < M; i++) {
        int x2y_len = dp[roads[i].end].first;
        int x2y_val = dp[roads[i].end].second;
        if (roads[i].val > dp[roads[i].start].second &&
            dp[roads[i].start].first + 1 > dp[roads[i].end].first) {
            x2y_len = dp[roads[i].start].first + 1;
            x2y_val = roads[i].val;
            result = max(x2y_len, result);
        }
        // the other side
        int y2x_len = dp[roads[i].start].first;
        int y2x_val = dp[roads[i].start].second;
        if (roads[i].val > dp[roads[i].end].second &&
            dp[roads[i].end].first + 1 > dp[roads[i].start].first) {
            y2x_len = dp[roads[i].end].first + 1;
            y2x_val = roads[i].val;
            result = max(y2x_len, result);
        }
        dp[roads[i].end].first = x2y_len;
        dp[roads[i].end].second = x2y_val;
        dp[roads[i].start].first = y2x_len;
        dp[roads[i].start].second = y2x_val;
    }
    return result;
}