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 .
Auto comment: topic has been updated by digishek (previous revision, new revision, compare).
I tested it and on TC33 it's doing between $$$2 \cdot 10^8$$$ and $$$3 \cdot 10^8$$$ iterations of the
gofunction, and the fact that it's a function probably is adding a relatively high constant factor. That's the best reason I have for why it's TLE'ing, as well as the fact that there's a TL of 1s and $$$maxn = 3 \cdot 10^5$$$, compared to the usual 2s and $$$maxn = 2 \cdot 10^5$$$I tried changing the adj loop so that you wouldn't create a copy of the edge every iteration, but that didn't work.
I also cleaned up the code here, if anyone better at this type of thing than me wants to take a look.
I initially thought "go" function will be called at max 2*(no of edges) times .
But seeing this , I can get some idea on why the solution is failing.
Thanks