Codeforces 459E- Pashmak and Graph

Problem Statement:
459E - Pashmak and Graph

Solution:
A graph problem which solution does not require building any graph at all :P Things to note are that the edges are directed, and all valid path are strictly increasing. We can view this problem as an extension to the classical longest increasing subsequence, but instead of a nice linear array, we have a directed graph here. Let's define L[u] as the longest increasing weight path starting from vertex u.

How can this representation useful? Firstly, we sort the edges according to their weights. Then we iterate over the edges from the heaviest to the lightest:
1. Suppose the current edge is pointing from u to v. Here we know that L[v] is the length of longest increasing weight path starting at v using all edges heavier than w(u,v). Then we can simply have L[u] = max {L[u], L[v] + 1}
2. However, there are cases where some edges share the same weights. As such, we need to consider all such edges together, before updating the values of each L[u] to maintain the "increasing weight" property in 1.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
int INF = (int) 1e9;
vector<pair<int,pair<int,int> > > st;
int dp[300005];
int N, M;
int main(){
    int u,v,w;
    scanf("%d%d", &N, &M);
    for(int i=0;i<M;++i){
        scanf("%d %d %d", &u,&v,&w);
        st.push_back(make_pair(w,make_pair(u,v)));
    }
    sort(st.begin(),st.end());
    int ans = 0;
    vector<pair<int,int> > p;
    for(int i=M-1;i>=0;--i){
        w = st[i].first;
        u = st[i].second.first;
        v = st[i].second.second;
        int tmp = max(1, max(dp[u], 1+dp[v]));
        p.push_back(make_pair(u,tmp));
        if(i==0 || w != st[i-1].first){
            while(!p.empty()){
                pair<int,int> cur = p.back();
                p.pop_back();
                dp[cur.first] = max(dp[cur.first],cur.second);
                ans = max(ans, dp[cur.first]);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}