627 - The Net

[moudud99]

Thanks Brainfry I found my mistake...
Funny problem with a bad input system

[richatibrewal]

I wrote the code for this problem. I dont know why I am getting RunTime Error

Code: Select all

#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#define MAXLEN 500
#define INF 1000000000
using namespace std;

vector<vector<int> > graph;
int parent[MAXLEN][MAXLEN],dist[MAXLEN][MAXLEN];

void find_distance()
{
    int u,v,i,j,n;
    bool visited[MAXLEN];

    n = graph.size();
    for(i=0;i<n;i++)
    {
        memset(visited,false,sizeof(visited));
        queue<int> q;
        q.push(i);
        visited[i] = true;

        while(!q.empty())
        {
            u = q.front();
            q.pop();

            for(j=0;j<graph[u].size();j++)
            {
                v = graph[u][j];
                if(!visited[v])
                {
                    visited[v] = true;
                    dist[i][v] = dist[i][u]+1;
                    parent[i][v] = u;
                    q.push(v);
                }
            }
        }
     }
}

int main()
{
    int m,n,i,u,v,j;
    char str[100000];

    while(scanf("%d",&n)!=EOF)
    {
        graph.clear();
        for(i=0;i<n;i++)
        {
            vector<int> r;
            graph.push_back(r);

            for(j=0;j<n;j++)
            {
                parent[i][j] = -1;
                if(i==j)
                    dist[i][j] = 0;
                else
                    dist[i][j] = INF;
            }
        }

        for(i=0;i<n;i++)
        {
            scanf("%s",str);

            j = 0;
            u = 0;
            while(str[j]!='-')
                u = u*10 + (str[j++]-'0');
            j++;

            u--;
            for(v=0;j<strlen(str);j++)
            {
                if(str[j]==',')
                {
                    v--;
                    graph[u].push_back(v);
                    v = 0;
                }
                else
                {
                    v = (v*10) + (str[j]-'0');
                }

                if(j==strlen(str)-1)
                {
                    v--;
                    graph[u].push_back(v);

                }
            }
        }

        find_distance();
        scanf("%d",&m);

        printf("-----\n");
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);

            u--;
            v--;
            if(dist[u][v]==INF)
                printf("connection impossible\n");
            else
            {
                stack<int> st;
                j = parent[u][v];

                st.push(v);
                while(j!=-1)
                {
                    st.push(j);
                    j = parent[u][j];
                }

                printf("%d",st.top()+1);
                st.pop();
                while(!st.empty())
                {
                    printf(" %d",st.top()+1);
                    st.pop();
                }
                printf("\n");
            }
        }
    }
    return 0;
}

I tries with all the test cases I could but still could not resolve the error.

Help me!!

[lighted]

As i see in this thread, several people get RE. I think problem is in judge's input. Maybe judge's input contains input like this

Code: Select all

2
1-2
2-1,
1
1 2

I added one check in your code and your code got accepted.

[moxlotus]

Not too sure what is wrong with the code, I have tried the inputs from uDebug and got everything correct. but keeps getting WA on UVa.
Anyone has any better test case for me to try out?

Code: Select all

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define SWAP(a,b) a^=b^=a^=b 
#define ALL(x) (x).begin(), (x).end()
#define ALLA(a,n) a, a+(n)
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define oo 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vip;
typedef vector<vector<int> > vii;
typedef vector<vector<pair<int, int> > > viip;

int N, M, a, b, visited[305];
vii adjList;
string line;
char c;
int main(int argc, char **argv){
  std::ios::sync_with_stdio(false);
  while(cin >> N){
    getline(cin, line);
    adjList.assign(N+1, vi());
    FOR(i,0,N){
      getline(cin, line); 
      vi v;
      stringstream ss(line);
      ss >> a >> c;
      while(ss.good()){
        ss >> b >> c;
        v.PB(b);
      }
      adjList[a] = v;
    }
    cin >> M;
    cout << "-----" << endl;
    while(M--){
      memset(visited, 0, sizeof(visited));
      cin >> a >> b;
      queue<int> q;
      q.push(a);
      visited[a]=a;
      while(!q.empty()){
        int u = q.front(); q.pop();
        if(u == b) break; 
        vector<int> next = adjList[u];
        for(auto it = next.begin(); it != next.end(); ++it){
          int v = *it;
          if(!visited[v]){
            visited[v]=u;
            q.push(v);
          }
        }
      }
      stack<int> path;
      path.push(b);
      while(b != visited[b] && b){
        b = visited[b];
        path.push(b);
      }
      if(path.top() == a){
        while(!path.empty()){
          b = path.top(); path.pop();
          cout << b;
          if(!path.empty()) cout << " ";
          else cout << endl;
        }
      } else cout << "connection impossible" << endl;
    }
  }
  return 0;
}