336 - A Node Too Far

[Scarecrow]

why am I getting RE in this problem? can't figure it out. can any1 help plz?

Code: Select all

AC

[brianfry713]

TTL can be greater than 50.

[Scarecrow]

fixing the RE, now i get WA

Code: Select all

AC

[brianfry713]

There is a case where a node is connected to itself. This causes your graph to be constructed incorrectly.

[shatil_cse]

WA !!!!!!
please help me..........

Code: Select all

#include<stdio.h>
int a,t,front,rear,level,nc,q[100000],i,j,k,l,m,n,x[10000][10000],y[10000],z[100000],state[10000];
int main()
{
	scanf("%d",&nc);
	for(l=1;nc!=0;l+=j-1)
	{
		for(i=0;i<10000;i++) x[i][0]=1;
		t=0;
		for(i=1;i<=nc;i++)
		{
			scanf("%d%d",&m,&n);                     //I have store all node I can go directly from a node(index) in two dimentional array
													 //x[m][0] indicates how many node I can go from node m.
			if(x[m][0]==1) t++;
			x[m][x[m][0]++]=n;
			if(x[n][0]==1) t++;
			x[n][x[n][0]++]=m;
		}
		scanf("%d%d",&y[1],&z[1]);
		for(k=1;y[k]!=0||z[k]!=0;) scanf("%d%d",&y[k],&z[++k]);       
		for(j=1;j<k;j++)
		{
			for(i=0;i<10000;i++) state[i]=0;             //initializing the state 
			rear=1;
			front=1;
			level=1;
			a=0;
			q[rear]=y[j];
			n=y[j];
			for(i=1;rear>=front&&a!=z[j];i++)           //traversing the node.
			{
				state[n]++;
				for(m=1;m<x[n][0];m++)
				{
					if(state[x[n][m]]==0)
					{
						q[++rear]=x[n][m],state[x[n][m]]++;
					}
				}
				if(front==level) level=rear,a++;
				n=q[++front];
			}
			printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",l+j-1,t-rear,y[j],z[j]);
		}
		scanf("%d",&nc);
	}
	return 0;
}

[brianfry713]

Edit: removed wrong I/O.

[mahade hasan]

cut

[binitam]

Code: Select all

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main()
{
	int nc,nEdge,a,b,i,root,ttl,cases=1;
	while(1)
	{
		
		
			vector<int>edges[10000];
			cin>>nc;
			
			if(nc==0)break;
		
			for(i=0;i<nc;i++)
			{
				cin>>a>>b;
				if(a==0&&b==0)break;
				edges[a].push_back(b);
				edges[b].push_back(a);
				

			}
			while(1)
			{
				int v,visited[10000]={0},dist[10000]={0},u,count=0,flag=0;
				
				cin>>root>>ttl;
				if(root==0&&ttl==0)
				{
					flag=1;

					break;
				}
				queue<int>q;
				q.push(root);
				while(!q.empty())
				{
					v=q.front();
					visited[v]=1;
					for(i=0;i<edges[v].size();i++)
					{
						u=edges[v][i];

						if(!visited[u])
						{
							visited[u]=1;
							dist[u]=dist[v]+1;
							
							if(dist[u]>ttl)count++;

							q.push(u);
						}


					}
					q.pop();
					
				}
				if(!flag)
				cout<<"Case "<<cases<<": "<<count<<" nodes not reachable from node "<<root<<" with TTL = "<<ttl<<"."<<'\n';
				cases++;

			}

	}
	return 0;
}

IT IS GIVING WA,,,cant understand,,plz help


[quote][/quote]

[brianfry713]

mahade hasan, running memset on your large MainArry every test case is slow. no network will contain more than 30 nodes. My AC code assumes each node can be any 32-bit signed integer.

[brianfry713]

binitam, no network will contain more than 30 nodes. My AC code assumes each node can be any 32-bit signed integer.

[@ce]

Getting WA...plz help

Code: Select all

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<deque>
#include<queue>
#include<map>
#include<utility>

#define L long long int
#define U unsigned long long int
using namespace std;

int arr[111][111];
map <int,int>m;
vector < pair<int,int> >v;

main()
{
      int t = 1;
      while(1)
      {
            int n,p=0;
            cin>>n;
            m.clear();
            v.clear();
            if(!n)
                  break;
            for(int i = 0;i<n;i++)
            {
                  int a,b;
                  cin>>a>>b;
                  if(!(a|b))
                        break;
                  //cout<<a<<b<<endl;
                  if(m.find(a) == m.end())
                        m.insert(make_pair(a,p++));
                  if(m.find(b) == m.end())
                        m.insert(make_pair(b,p++));
                  v.push_back(make_pair(a,b));

            }

            for(int i = 0;i<m.size();i++)
            {
                  for(int j = 0;j<m.size();j++)
                        arr[i][j] = -1;
            }
            for(int i = 0;i<n;i++)
            {
                  int a = m.find(v[i].first)->second ;
                  int b = m.find(v[i].second)->second;
                  arr[a][b] = 1;
                  arr[b][a] = 1;
            }

            for(int k = 0;k<m.size();k++)
            {
                  for(int i= 0;i<m.size();i++)
                  {
                        for(int j = 0;j<n;j++)
                        {
                              if(i == j)
                                    arr[i][j] = 0;
                              else if(arr[i][j] == -1)
                              {
                                    if(arr[i][k] != -1 && arr[k][j] != -1)
                                          arr[i][j] = arr[i][k] + arr[k][j];
                              }
                              else
                              {
                                    if(arr[i][k] != -1 && arr[k][j] != -1)
                                          arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
                              }
                        }
                  }
            }

            int src,ttl;
            while(1)
            {
                  cin>>src>>ttl;
                  if(!(src|ttl))
                        break;
                  int c = 0;
                  for(int i = 0;i<m.size();i++)
                  {
                        if(src == i)
                              continue;
                        int x = m.find(src)->second;
                        if(arr[x][i] > ttl || arr[x][i] == -1)
                              c++;
                  }
                  printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",t++,c,src,ttl);
            }
      }
}

[brianfry713]

@ce, I was able to make your code AC with two small changes.
In Floyd-Warshall, all the limits should be m.size().
On line 93 you have

Code: Select all

                        if(src == i)
                              continue;

Delete that and check if(x==i) instead.

[alimbubt]

I am getting continuously WA.....Please help me or give me some critical test case in which my code shows wrong answer..

Code: Select all

#include<cstdio>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<bitset>
#include<string>
#include <sstream>
#include <fstream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define pi 2*acos(0.0)
using namespace std;

int BFS(int start,int ttl);
vector<int>adj[40];
vector<int>vec;
map<int,int>mp;

int main()
{
    int nc,node,i,f,u,v,j,start,ttl,t=0;
    while(scanf("%d",&nc)==1)
    {
        if(nc==0) break;
        f=0;
        for(i=1;i<=nc;i++)
        {
            scanf("%d%d",&u,&v);
            if(mp[u]==0)
            {
                mp[u]=++f;
                vec.push_back(mp[u]);
            }
            if(mp[v]==0)
            {
                mp[v]=++f;
                vec.push_back(mp[v]);
            }
            adj[mp[u]].push_back(mp[v]);
            adj[mp[v]].push_back(mp[u]);
        }
        sort(vec.begin(),vec.end());
        node=vec.size();
        while(scanf("%d%d",&start,&ttl)==2)
        {
            int count;
            if(start==0&&ttl==0) break;
            int start1=start;
            if(mp[start]==0)
            {
                printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++t,vec.size(),start1,ttl);
                continue;
            }
            start=mp[start];
            count=BFS(start,ttl);
            printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++t,vec.size()-count,start1,ttl);
        }
        for(i=1;i<=node;i++)
        adj[i].clear();
        vec.clear();
        mp.clear();
    }
    return 0;
}


int BFS(int start,int ttl)
{
    int dist[50]={0};
    int count=1,i;
    map<int,int>mpp;
    mpp[start]=1;
    queue<int>q;
    q.push(start);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(i=0;i<adj[u].size();i++)
        {
            int v=adj[u][i];
            dist[v]=dist[u]+1;
            mpp[v]++;
            if(mpp[v]>1) continue;
            if(dist[v]<=ttl)
            count++;
            if(dist[v]<=ttl-1)
            q.push(v);
        }
    }
    mpp.clear();
    return count;
}

[brianfry713]

Input

Code: Select all

2
1 1  1 2
1 1  0 0

0

Correct output:

Code: Select all

Case 1: 0 nodes not reachable from node 1 with TTL = 1.

[sumit saha shawon]

why I am getting WA??
My code:

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<string.h>
using namespace std;
int main()
{
int edges;
int x,y;
int src,ttl,kase=1;
vector<int>G[100000];
set<int>s;

while(cin>>edges&&edges)
{
// cout<<edges<<endl;
// memset(G,0,sizeof G);
for(int i=0;i<100000;i++)
G.clear();
s.clear();

for(int i=1; i<=edges; i++)
{
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
s.insert(x);
s.insert(y);

}
// cout<<s.size()<<endl;
while(cin>>src>>ttl)
{
int count=1;
if(src==0&&ttl==0)
break;
// printf("Case %d: %d %d\n",kase++,src,ttl);
queue<int>q;
q.push(src);
int visited[100000]= {0},dis[100000];
visited[src]=1,dis[src]=0;
while(!q.empty())
{
int u=q.front();
for(int i=0; i<G.size(); i++)
{
int v=G;
if(!visited[v])
{

dis[v]=dis+1;
if(dis[v]>ttl)
break;
q.push(v);
visited[v]=1;

count++;


}

}
q.pop();
}
// cout<<s.size()-count<<endl;
int ans=s.size()-count;
if(ans<0)
ans=0;
printf("Case %d: %d nodes not reachable from node %d with TTL = %d\n.",kase++,ans,src,ttl);


}



}

}