336  A Node Too Far
Moderator: Board moderators
Hi all,
I got ACC  so no need to answer. Thanks anyway.
What have I learnt ? Just to share it , so that it is easier for
the others which face same problems later.
1) Using Claudio's approach
( new vertices defined in queries ) I can get ACC.
2) Using mf's approach ( not defining new vertices when I
meet these vertices only in queries ) I also get ACC.
Judging from 1) and 2) I could say the Judge data does not contain
such cases. I mean all queries ( X, some_ttl ) include only such
values for X which have previously been mentioned in the
edge's list.
3) Maybe the most important thing to note is why I was
getting WA at the moment I wrote the previous post.
Well, my problem was the following: I was assuming the numbers
given in the input are separated by at least one SPACE.
Well, the Judge has cases in which the numbers are separated
only by TABs ( no spaces ).
I got ACC  so no need to answer. Thanks anyway.
What have I learnt ? Just to share it , so that it is easier for
the others which face same problems later.
1) Using Claudio's approach
( new vertices defined in queries ) I can get ACC.
2) Using mf's approach ( not defining new vertices when I
meet these vertices only in queries ) I also get ACC.
Judging from 1) and 2) I could say the Judge data does not contain
such cases. I mean all queries ( X, some_ttl ) include only such
values for X which have previously been mentioned in the
edge's list.
3) Maybe the most important thing to note is why I was
getting WA at the moment I wrote the previous post.
Well, my problem was the following: I was assuming the numbers
given in the input are separated by at least one SPACE.
Well, the Judge has cases in which the numbers are separated
only by TABs ( no spaces ).
Surely, the fastest one ATMSedefcho wrote:Hello all,
1. Is Claudio's output from an ACC program ?
I guess so.
Yes, my program adds nodes found in queries to the network and it seems that mf's solution doesn't.Sedefcho wrote:I tend to think ( I am quite sure ) Claudio does the same in
his program and it seems mf does the
opposite ( does not define new vertices in such cases ).
At least that explains perfectly the differences which
mf mentions.
Any ideas are welcome.
My program also tolerates duplicated edges although the problem statement explicitly says that there aren't any in input. In the sample I posted there are cases with self edges and duplicated edges.
Ciao!!!
Claudio
CDiMa,i'm afraid ur code is wrong
just look at this group of input and output u apply to us
5
1 2 2 3 3 1 4 5 6 2147483647
1 1
ur program's output is 5
which should be 4
isn't it?
and i also got WA,hope someone can help me out
i used a function
to store vertices
and my input is
so what's wrong with my code?
full program
just look at this group of input and output u apply to us
5
1 2 2 3 3 1 4 5 6 2147483647
1 1
ur program's output is 5
which should be 4
isn't it?
and i also got WA,hope someone can help me out
i used a function
Code: Select all
int lookup(int n)
{
int i;
for(i = 0;i < numOfNodes;i++)
{
if(hash[i] == n) return i;
}
hash[i] = n;
numOfNodes++;
return i;
}
and my input is
Code: Select all
graph[lookup(beg)][lookup(end)] = graph[lookup(end)][lookup(beg)] = 1;
full program
Code: Select all
#include <iostream>
using namespace std;
#define MAX_NODE 100
int graph[MAX_NODE][MAX_NODE];
int visited[MAX_NODE];
int hash[MAX_NODE];
int ttl;
int cnt;
int numOfNodes;
void initGraph()
{
int i,j;
for(i = 0;i < MAX_NODE;i++)
{
visited[i] = 0;
for(j = 0;j < MAX_NODE;j++)
graph[i][j] = 0;
}
}
void init()
{
ttl = cnt = numOfNodes = 0;
initGraph();
for(int i = 0;i < MAX_NODE;i++)
{
hash[i] = 1;
}
}
int lookup(int n)
{
int i;
for(i = 0;i < numOfNodes;i++)
{
if(hash[i] == n) return i;
}
hash[i] = n;
numOfNodes++;
return i;
}
void bfs(int begin,int ttl)
{
visited[begin] = 1;
if(ttl == 0) return;
int i;
for(i = 0;i < MAX_NODE;i++)
{
if(graph[begin][i] == 1 && visited[i] == 0)
{
cnt++;
bfs(i,ttl  1);
}
}
}
int main()
{
int Cases = 1;
int numOfEdge;
int i;
int beg,end;
int start;
while(cin >> numOfEdge)
{
if(numOfEdge == 0) break;
init();
for(i = 0;i < numOfEdge;i++)
{
cin >> beg >> end;
graph[lookup(beg)][lookup(end)] = graph[lookup(end)][lookup(beg)] = 1;
}
while(cin >> start >> ttl)
{
if(start == 0 && ttl == 0) break;
bfs(lookup(start),ttl);
cout << "Case " << Cases++ << ": " << numOfNodes  cnt  1 << " nodes not reachable from node " << start << " with TTL = " << ttl << "." << endl;
ttl = cnt = 0;
for(i = 0;i < numOfNodes;i++)
visited[i] = 0;
}
}
return 0;
}
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know this will lead to knowledge."Confucius
"Hold what you really know and tell what you do not know this will lead to knowledge."Confucius
Hmmm, I applied this sample to my program and it replied 4...Morning wrote:CDiMa,i'm afraid ur code is wrong
just look at this group of input and output u apply to us
5
1 2 2 3 3 1 4 5 6 2147483647
1 1
ur program's output is 5
which should be 4
isn't it?
Then I rerun my program on the big sample and it replied 4 again...
So my sample posted is indeed wrong but my program is right.
What I find amazing is that the source code was last modifiend on Apr 20 2004 and the output of my big sample is dated Mar 18 2005.
So I didn't change the source code since I produced the output!!!
Ciao!!!
Claudio
If I understand it correctly your bfs isn't a real bfs...Morning wrote:Code: Select all
void bfs(int begin,int ttl) { visited[begin] = 1; if(ttl == 0) return; int i; for(i = 0;i < MAX_NODE;i++) { if(graph[begin][i] == 1 && visited[i] == 0) { cnt++; bfs(i,ttl  1); } } }
Ciao!!!
Claudio
It is:Morning wrote: yeah,it's dfs,actually.
but it isnt why i got WA,is it?
Code: Select all
4
1 2 2 3 3 4 1 3
1 2 0 0
0
Ciao!!!
Claudio
I've understand what's wrong with my code
Thank u,MDima
but here's another problem,my code always get TLE now
i even change my graph data structure from adj matrix to adj list,but still got TLE,can u tell me why?
is there any wired input data in test case?like a node presented by a string?
and i've tried to send the standard sample solution of this problem to judger,and got TLE,too
so wired
Thank u,MDima
but here's another problem,my code always get TLE now
i even change my graph data structure from adj matrix to adj list,but still got TLE,can u tell me why?
is there any wired input data in test case?like a node presented by a string?
Code: Select all
#include <iostream>
using namespace std;
#define MAX_NODE 31
int graph[MAX_NODE][MAX_NODE];//now it is a adj list
int numOfLinkNode[MAX_NODE];//help to count numberOfLinkNode of every node
int visited[MAX_NODE];
int hash[MAX_NODE];
int ttl;
int cnt;
int numOfNodes;
void initGraph()
{
int i;
for(i = 0;i < MAX_NODE;i++)
{
visited[i] = 0;
numOfLinkNode[i] = 0;
}
}
void init()
{
ttl = cnt = numOfNodes = 0;
initGraph();
for(int i = 0;i < MAX_NODE;i++)
{
hash[i] = 1;
}
}
int lookup(int n)
{
int i;
for(i = 0;i < numOfNodes;i++)
{
if(hash[i] == n) return i;
}
hash[i] = n;
numOfNodes++;
return i;
}
void bfs(int begin,int ttl)
{
visited[begin] = 1;
if(ttl == 0) return;
int i;
for(i = 0;i < numOfLinkNode[begin];i++)
{
if(visited[graph[begin][i]] == 0) cnt++;
bfs(graph[begin][i],ttl  1);
}
}
int main()
{
int Cases = 1;
int numOfEdge;
int i;
int beg,end;
int start;
while(cin >> numOfEdge)
{
if(numOfEdge == 0) break;
init();
for(i = 0;i < numOfEdge;i++)
{
cin >> beg >> end;
beg = lookup(beg);
end = lookup(end);
graph[beg][numOfLinkNode[beg]++] = end;
graph[end][numOfLinkNode[end]++] = beg;
}
while(cin >> start >> ttl)
{
if(start == 0 && ttl == 0) break;
bfs(lookup(start),ttl);
cout << "Case " << Cases++ << ": " << numOfNodes  cnt  1 << " nodes not reachable from node " << start << " with TTL = " << ttl << "." << endl;
cnt = 0;
for(i = 0;i < numOfNodes;i++)
visited[i] = 0;
}
}
return 0;
}
so wired
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know this will lead to knowledge."Confucius
"Hold what you really know and tell what you do not know this will lead to knowledge."Confucius
I don't think there is any weird input such as non integer nodes, as I would fail too.Morning wrote:I've understand what's wrong with my code
Thank u,MDima
but here's another problem,my code always get TLE now
i even change my graph data structure from adj matrix to adj list,but still got TLE,can u tell me why?
is there any wired input data in test case?like a node presented by a string?
If I understand your code correctly your program is slow because the recursion in your bfs is wrong. A standard bfs would take O(e) where e is the number of edges in the connected component of the starting node. Your recursion terminates when ttl drops to 0 and so I think your complexity reaches something like O(ttl*e^2)
Ciao!!!
Claudio
CDiMa,thank u indeed,u helped me a lot.
I've correct my code,but it still get WA.but i hope i can find the mistakes myself.
Anyway,thanks again :)
I've correct my code,but it still get WA.but i hope i can find the mistakes myself.
Anyway,thanks again :)
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know this will lead to knowledge."Confucius
"Hold what you really know and tell what you do not know this will lead to knowledge."Confucius
336__HELPPPP!!!
i cann't get wrong of my code. It gets runtime error.
Please help anyone.
Is the numbers cannot be stored in long?
here my code:
Please help anyone.
Is the numbers cannot be stored in long?
here my code:
Code: Select all
#include<stdio.h> // RUNTIME ERROR
#define MAX 35
int end, head, number, connection, vertex, ttl, count;
int distance[MAX], queue[MAX*MAX], graph[MAX][MAX];
long value[MAX];
char color[MAX];
void enqueue(int u)
{
queue[end++]=u;
number++;
}
int dequeue()
{
number;
return queue[head++];
}
void bfs(int s)
{
int i, u;
for(i = 0;i < vertex; i++) // n => no. of vertex
{
if(i != s) // s => source
{
color[i] = 'w';
distance[i] = 32560;
}
}
color[s] = 'g';
distance[s] = 0;
queue[0] = '/0';
number = 0; head = 1; end = 1;
enqueue(s);
while(number)
{
u = dequeue();
for(i = 0;i < vertex; i++)
{
if(graph[u][i])
{
if(color[i]=='w')
{
color[i]='g';
distance[i]=distance[u]+1;
if(distance[i] > ttl) count++;
enqueue(i);
}
}
}
color[u]='b';
}
}
void main()
{
int i, j, kase = 1;
long from, to, u, v, start;
freopen("E:\\test.txt", "rt", stdin);
while((scanf("%d",&connection)==1) && connection)
{
for(i = 0; i < MAX; i++)
value[i] = 0;
for(i = 0;i < MAX; i++)
for(j = 0; j < MAX; j++)
graph[i][j] = 0;
vertex=0;
for(i = 0; i < connection; i++)
{
scanf("%ld %ld", &from, &to);
u = 1;v = 1;
for(j = 0; j < vertex; j++)
if(value[j] == from)
u = j;
else if(value[j] == to)
v = j;
if(u == 1)
{
u = vertex;
value[vertex++] = from;
}
if(v == 1)
{
v = vertex;
value[vertex++] = to;
}
//graph[u][v] = 1;
//graph[v][u] = 1;
if (u != v) graph[u][v] = graph[v][u] = 1;
}
while(scanf("%ld %d", &start, &ttl) == 2)
{
if((start == 0) && (ttl == 0)) break;
count = 0;
for(j = 0; j < vertex; j++)
if(value[j] == start)
u = j;
bfs(u);
/* For unconnected nodes*/
for(i = 0; i < vertex; i++)
if(color[i] == 'w')
count++;
printf("Case %d: %d nodes not reachable from node %ld with TTL = %d.\n", kase++, count, start, ttl);
}
}
}
roni(SUST)
336 A node too far. WA getting mad. Plz someone help
I used BFS to solve this.But its givin WA. I don't know why. I've tried lots of input (including loops,disconnected network). All is correct. But Still having WA. Plz some one help.
Should i have 2 consider cases where a node is not in the description but is in the query. Like:
Pleaze help me(with tricky inputs,suggetions anything);
Shihab
Should i have 2 consider cases where a node is not in the description but is in the query. Like:
My code is:4
0 0 1 2 2 3 3 3
5 1 0 0
Code: Select all
//removed after AC
Shihab
Last edited by shihabrc on Thu Jan 05, 2006 10:19 pm, edited 1 time in total.
Shihab
CSE,BUET
CSE,BUET

 Experienced poster
 Posts: 161
 Joined: Tue Oct 25, 2005 8:38 pm
 Location: buet, dhaka, bangladesh
Re: 336 A node too far. WA getting mad. Plz someone help
No, there wont be such casesshihabrc wrote:Should i have 2 consider cases where a node is not in the description but is in the query.
ishtiak zaman

the world is nothing but a good program, and we are all some instances of the program

the world is nothing but a good program, and we are all some instances of the program