salt_n_ice's blog

CSES Longest Flight Route TLE in one test case
By salt_n_ice, history, 3 years ago, In English

Problem : Link. I simply did bfs from node 1 and found the maximum distance from this node to all other nodes

Code

So the solution is O(n+m) but still, there is TLE in one case. Why?

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

tried to do the same, got TLE on the LAST Test Case. Solved the problem with topological sort. Link to code https://cses.fi/paste/95851f6ac3e4e45919f087/

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Understood, thanks

    → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    https://cses.fi/paste/9ee3d2f988dc939e6047e1/ :New

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      nice solution but I didnt understand few things like why we have to do toposort for 2 times and why you are not pushing it into the queue in topo function. Can you please explain your intuition and thought process that will be really helpful.Thanks in advance :)))

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ` You can solve it by using one toposort also.. (Accepted soln) ~~~~~

        #include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
 
//------------------------Actual Code Starts Here-----------
 
void dfs(ll node,vector<ll>&vis,vector<vector<ll>>&g,stack<ll>&s){
    vis[node]=1;
    for(auto child:g[node]){
        if(vis[child]==0){
            dfs(child,vis,g,s);
        }
    }
    s.push(node);
}
 
void solve(){
        ll n,m;cin>>n>>m;
        vector<vector<ll>>g(n+1) ;
        vector<ll>vis(n+1,0);
        stack<ll>s;
        for(ll i=0;i<m;i++){
            ll a,b;cin>>a>>b;
            g[a].push_back(b);
        }
        vector<ll>dis(n+1,-1e9);
        vector<ll>par(n+1,0);
 
        // do toposort(ohoho);
        for(ll i=1;i<=n;i++){
            if(vis[i]==0){
                dfs(i,vis,g,s);
            }
        }
        if(s.size()!=n){
            cout<<"IMPOSSIBLE"<<endl;return;
        }
        dis[1]=0;
        while(!s.empty()){
            ll node=s.top();
            s.pop();
            for(auto child:g[node]){
                if(dis[node]!=-1e9&&dis[child]<dis[node]+1){
                    dis[child]=dis[node]+1;
                    par[child]=node;
                }
            }
        }
        if(dis[n]==-1e9){
            cout<<"IMPOSSIBLE"<<endl;
        }
        else{
            vector<ll>path;
            path.push_back(n);
            while(n!=1){
                n=par[n];
                path.push_back(n);
            }
            cout<<path.size()<<endl;
            for(ll i=path.size()-1;i>=0;i--){
                cout<<path[i]<<" ";
            }
        }
        
 
  
}
 
signed main(){
 //faster input and output
std::ios::sync_with_stdio(false);
std::cin.tie(0);
ll t=1;
// cin>>t;
while(t--){
     solve();
  }
    return 0;
}
 ~~~~~

        `

        → Reply
      • »
        »
        »
        »
        6 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        https://cses.fi/paste/9ee3d2f988dc939e6047e1/ for this solution .

        Initially, we execute the toposort algorithm without considering node 1. Consequently, all nodes reachable from node 1 will have a parent value of -1. This is because we can reach these nodes from node 1, and node 1 is not included in our queue. Therefore, there is always at least one edge ensuring that the indegree for these nodes remains nonzero. In cases where the indegree is not zero, the parent value for these nodes is always set to -1.

        Towards the end of the process, we backtrack from node n to node 1 by following their parent relationships to determine the longest path. However, because we did not include node 1 in our initial queue, we will not reach any nodes that are reachable from node 1. To illustrate this point, consider the following example:

        10 10

        3 9 6 5 6 9 2 8 4 8 1 2 7 10 7 6 7 5 8 10

        Without including node 1, the parent array appears as follows: -1 -1 -1 -1 -1 6 7 -1 -1 6 -1.

        Now, it's evident that node n is marked with -1, which indicates that there is either at least one path between node 1 and n or no path exists at all. If we execute toposort while including node 1, only nodes reachable from node 1 will have their parent values altered. The resulting parent array will look like this: -1 -1 1 -1 -1 6 7 -1 2 6 8.

        However, it's important to note that including node 1 in the initial toposort call does not guarantee that we will always be able to backtrack from node n to 1, as we do in this solution.

        → Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think test cases are weak in CSES for this problem.

AC on Date: 13/09/2022

vector<ll> p[N];
void solve(){
    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<m;i++){
        ll a,b;
        cin>>a>>b;
        --a,--b;
        p[a].pb(b);
    }
    vector<int> dist(n,0);
    ll last[n];
    for(ll i=0;i<n;i++) last[i]=i;
    stack<ll> q;
    q.push(0);
    while(!q.empty()){
        int x=q.top();
        q.pop();
        for(auto i:p[x]){
            if((dist[x]+1)>dist[i]){
                dist[i]=dist[x]+1;
                last[i]=x;
                q.push(i);
            }
        }
    }
    if(dist[n-1]==0){
        cout<<"IMPOSSIBLE"<<endl;
        return;
    }
    ll i=n-1;
    vector<ll> ans;
    // for(ll i=0;i<n;i++){
    //     cout<<last[i]<<" ";
    // }
    // cout<<endl;
    ans.pb(i);
    while(i!=0){
        i=last[i];
        ans.pb(i);
    }
    reverse(all(ans));
    cout<<(ll)ans.size()<<endl;
    for(auto i:ans){
        cout<<(i+1)<<" ";
    }
    cout<<endl;
}
signed main(){
    fastio();
    solve();
    return 0;
}
→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It is important to note that fraph is directed and doesnt contain any cycles, therefore the graph is DAG (Directed Acyclic Graph). Because of this, we can easily use dp on ths graph, but first we have to topologically sort the nodes.

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Solved Using Topological Sort.

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone explain me why simple BFS gives TLE, and it seems O(n+m) but then what is the correct time complexity of the simple BFS solution?2) Complexitylease give a illustration of graph that shows O(m^2) complexity.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please suggest the error ? It is giving tle... ~~~~~

include <bits/stdc++.h>

using namespace std;

define int long long

signed main() { int n, m; cin >> n >> m; vector adj[n]; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u-1].push_back(v-1); } stackpq; vectordistance(n,0); //priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // int distance[n]; int parent[n]; for(int i=0;i<n;i++){ parent[i]=i; //distance[i]=0; } // distance[1] = 0; pq.push(0); while (!pq.empty()) { // int dis = pq.front().first; int node = pq.top(); pq.pop(); // if (dis > distance[node]) continue; // Skip if already processed for (auto i : adj[node]) { int adjnode = i; /// int adjdis = i; if (distance[adjnode] < distance[node] + 1) { distance[adjnode] = distance[node] + 1; pq.push(adjnode); parent[adjnode] = node; } } } if (distance[n-1] ==0) { cout << "IMPOSSIBLE" << endl; // return; } else { vector ans; int node = n-1; ans.push_back(node); while (node != 0) { // Change the stopping condition to node != 1 node = parent[node]; ans.push_back(node);
}

// ans.pop_back();
    reverse(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (auto it : ans) {
        cout << it+1 << " ";
    }
}
return 0;

}

~~~~~

→ Reply