salt_n_ice's blog

CSES Longest Flight Route TLE in one test case
By salt_n_ice, history, 4 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 (12)
| Write comment?
»
4 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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Understood, thanks

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

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

    → Reply
    • »
      »
      »
      18 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
      • »
        »
        »
        »
        18 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
»
2 years 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
»
18 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
»
12 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
»
10 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
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The solution isn't O(n+m). The worst case would be O((n+m)^2).

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

can anybody please tell the intuition behind the topo sort.

→ Reply