## 336 - A Node Too Far

Moderator: Board moderators

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 336 WA

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

Code: Select all

``````AC
``````
Last edited by Scarecrow on Mon Jul 16, 2012 8:31 pm, edited 1 time in total.
Do or do not. There is no try.
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 336 WA

TTL can be greater than 50.
Check input and AC output for thousands of problems on uDebug!
Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 336 WA

fixing the RE, now i get WA

Code: Select all

``````AC
``````
Last edited by Scarecrow on Mon Jul 16, 2012 8:32 pm, edited 1 time in total.
Do or do not. There is no try.
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 336 WA

There is a case where a node is connected to itself. This causes your graph to be constructed incorrectly.
Check input and AC output for thousands of problems on uDebug!
shatil_cse
New poster
Posts: 11
Joined: Thu Apr 05, 2012 8:33 pm

### Re: 336 WA

WA !!!!!!

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 336 WA

Edit: removed wrong I/O.
Last edited by brianfry713 on Wed Oct 24, 2012 7:21 pm, edited 2 times in total.
Check input and AC output for thousands of problems on uDebug!
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Getting TLE!!!

cut
Last edited by mahade hasan on Sun Nov 04, 2012 1:49 am, edited 1 time in total.
we r surrounded by happiness
need eyes to feel it!
binitam
New poster
Posts: 1
Joined: Fri Jul 13, 2012 8:20 pm

### Re: 336 WA

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 336 WA

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.
Check input and AC output for thousands of problems on uDebug!
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 336 WA

binitam, no network will contain more than 30 nodes. My AC code assumes each node can be any 32-bit signed integer.
Check input and AC output for thousands of problems on uDebug!
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### Re: 336 WA

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);
}
}
}
``````
-@ce
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 336 WA

@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.
Check input and AC output for thousands of problems on uDebug!
alimbubt
New poster
Posts: 39
Joined: Tue Aug 07, 2012 10:40 pm
Contact:

### Re: 336 WA

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>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]);
}
}
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++)
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();
{
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;
}
``````
Give me six hours to chop down a tree and I will spend the first four sharpening the axe...(BUBT ILLUSION)
http://uhunt.felix-halim.net/id/155497
http://onlyprogramming.wordpress.com/
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 336 WA

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.``
Check input and AC output for thousands of problems on uDebug!
sumit saha shawon
New poster
Posts: 19
Joined: Tue Jun 26, 2012 9:19 pm

### Re: 336 WA

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

}

}

}