TLE in Ada and Cycle on SPOJ

general
, ,
1

Link to the problem: SPOJ.com - Problem ADACYCLE
My code:

#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int MAXN = 2005;
int n;
vector<vector<int>> adj(MAXN);
vector<int> len(MAXN,MAXN);

int main()
{
    FASTIO
    cin >> n;
    int x;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin >> x;
            if(x) adj[i].push_back(j);
        }
    }
    for(int i=0; i<n; i++)
    {
        vector<bool> color(n,0);
        vector<int> dist(n,0);
        queue<int> q;
        q.push(i);
        color[i] = 1;
        while(!q.empty())
        {
            int u = q.front();
            q.pop();

            for(int v : adj[u])
            {
                if(color[v] == 2) continue;
                if(color[v] == 1 && v == i) len[i] = min(len[i], dist[u]-dist[v]+1);
                if(color[v] == 0)
                {
                    color[v] = 1;
                    dist[v] = 1+dist[u];
                    q.push(v);
                }
            }

            color[u] = 2;
        }
    }
    for(int i=0; i<n; i++) cout << ((len[i] != 2005) ? to_string(len[i])+"\n" : "NO WAY\n");
    cout << "\n";
    return 0;
}

The time complexity of the above code is O(V x (V+E)) which in the worst case becomes O(V^3), but I really don’t know about any optimizations that I can apply here to get rid of that TLE. Can anyone please help me with this?

2

replace cout with printf and cin to scanf

2 Likes
3

I think you should use DFS with some preprocess.
In preprocess store the path distance till that node from parent node.

4

@hblord787 Thanks for your response :slightly_smiling_face:, but wouldn’t the time complexity remain the same?

5

Are you using adjacency list or adjacency matrix ?

6

after this line it should be break , isn’t it ?

7

Adjacency list.

8

Let me try :slightly_smiling_face:

9

And can you explain that preprocessing part a little more? I am curious. :slightly_smiling_face:

10

Tried. But doesn’t work.

11

Found this somewhere else as well, but it said that this doesn’t work.

12

My possible reasons :

  1. Because the path is one-way, the maximum path length that forms a loop is n, so when the bfs is greater than n, processing should be done.
  1. Because each point can only be used once at most, so for the marker array, only one-dimensional is needed to reduce the initialization time.
    I used this with some changes in your code and it got accepted.
    Do you want me to post the Solution ? or You will Solve it!
1 Like
13

Let me try. :slightly_smiling_face:
Maybe I’ll get back to you tomorrow if I am stuck.
Thanks.

1 Like
14

I will tell u in 10 minutes if my code works .

15

Just one thing, what does “bfs is greater than n” mean in point 1?

16

Hey solved In One GO –

vi adj[MAX];

lli bfs(lli src , lli n)
{
    queue<lli>q;
    bool vis[n+1]={0};
    lli parent[n+1]={0};
    vis[src]=1;
    parent[src]=-1;
    q.push(src);
    while(!q.empty())
    {
        lli u = q.front(); q.pop();
        
        for(auto xt : adj[u])
        {
            if(xt == src)
            {
                lli cnt = 0;
                while(u!=-1){
                        cnt++;
                        u = parent[u];
                        //cout<<u<<" ";
                    }
                    return cnt;
            }
            if(!vis[xt])
            {
                q.push(xt);
                vis[xt]=1;
                parent[xt] = u;
            }
        }
    }
    return -1;
    
    
}


int main(){
fastio
lli t=1;
//cin>>t;
//chandan2();
while(t--) {
    lli n;
    scanf("%d", &n);
    loop(i,n)
    {
        loop(j,n)
        {
            lli x;
            scanf("%d", &x);
            if(x==1)
                adj[i+1].pb(j+1);
        }
    }
    
    for(lli i=1;i<=n;i++)
    {
        lli val = bfs(i,n);
        if(val==-1)
            printf("NO WAY\n");
        else
            printf("%d\n", val);;
        
    }
    


  }
return 0;
}
3 Likes
17

“2vft6k - Online C++0x Compiler & Debugging Tool - Ideone.com”

18

UPDATE: Got an AC!!! :smile:
I used scanf and printf as suggested by @ssrivastava990 along with breaking the BFS once I found the cycle for a given node.

2 Likes
19

@hblord787 I have solved the problem now, but still can you please share your code, I might get to learn something from it. :slightly_smiling_face:

20

Solution link. :blush: