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 (4)
| Write comment?
»
2 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
»
9 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
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

using stack inplace of queue made it work

→ Reply