digishek's blog

By digishek, 3 years ago, In English

I have been trying a solve a problem ,but getting TLE on a solution which I think is correct , Link — https://codeforces.com/contest/459/problem/E

MY SOLUTION

1) Since every edge needs to be processed once , we can apply dfs and store maximum path considering each edge as a source.

2)Consider an edge from v to u with weight w ,then dp[u] = 1+ max( dp[i] -----dp[j]) where there exists edges from u to (i to j) with weight > w.

3) Then we find the max dp[] value and print it .

4) The number of edges are 3e5 and they are only processed once , so shouldn't it pass ?

Extra Info

1) My submission link https://codeforces.com/contest/459/submission/114428522

2) Struct "ee" stores {destination , weight , edge index } of edge in adj list of source

3) Functions go(destination ,weight ,edge index) is doing dfs and computing dp .

Editorial contains a dp solution with o(nlogn) time complexity , this should be o(n) according to me . Can you guys please help me .

Full text and comments »

Tags help, dp, tle
  • Vote: I like it
  • +5
  • Vote: I do not like it