Блог пользователя salt_n_ice

CSES Longest Flight Route TLE in one test case
Автор salt_n_ice, история, 4 года назад, По-английски

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?

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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/

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Understood, thanks

    → Ответить
  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 :)))

      → Ответить
      • »
        »
        »
        »
        17 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        ` 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;
}
 ~~~~~

        `

        → Ответить
»
2 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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;
}
→ Ответить
»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
11 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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;

}

~~~~~

→ Ответить
»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anybody please tell the intuition behind the topo sort.

→ Ответить