Page 1 of 9

### 336

Posted: Sat Oct 12, 2002 8:57 pm
Can anyone tell me why my solution got WA?

Test cases wich it fail will of great help!

[cpp]
/* A Node Too Far */

#include <stdio.h>

int grafo[30][30];
int dist[30][30];

int rotulo[30];
int max;
int get_rotulo(int k) {
for (int i=0;;++i) {
if (rotulo == k) {
return i;
} else if (rotulo < 0) {
rotulo = k;
max = i+1;
return i;

}
}
return -1;
}

int main() {
int n;
int caso = 0;
for (;;) {
scanf("%d",&n);
if (!n) {
break;
}
for (int i=0;i<30;++i) {
for (int j=0;j<30;++j) {
grafo[j] = dist[j] = 0;
if (i==j) {
dist[j] = 1;
}
}
rotulo = -1;
}
max = 0;
for (int i=0;i<n;++i) {
int x,y;
scanf("%d %d",&x, &y);
x = get_rotulo(x);
y = get_rotulo(y);
grafo[x][y] = grafo[y][x] = 1;
dist[x][y] = dist[y][x] = 1;
}
for (int k=0;k<max;++k) {
for (int i=0;i<max;++i) {
for (int j=0;j<max;++j) {
if ((dist[j] == 0 && dist[k] && dist[k][j])
|| (dist[j] && dist[i][k] && dist[k][j] && dist[i][j] > dist[i][k] + dist[k][j])) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
for (;;) {
int x, y;
int num = 0;
scanf("%d %d",&x,&y);
if (!x && !y) {
break;
}
x = get_rotulo(x);
for (int i=0;i<max;++i) {
if (dist[x][i]>y && x != i) {
++num;
}
}
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",
++caso,num,rotulo[x],y);
}
}
return 0;
}
[/cpp]

Thanks

Posted: Sat Oct 12, 2002 11:07 pm
Input:
4
1 2 2 3 4 5 5 6
1 5 1 1 4 2 0 0
0

Posted: Sun Oct 13, 2002 2:41 am
Just solved it...

The problem was when I cannot reach some node from another...

Thanx anyway!!

Posted: Sun Jan 19, 2003 11:04 pm
I'm getting WA all the time... I tried all the example test cases, the one above and some other inputs, specially some with no connection between 2 networks... if anyone knows of some special input, please tell me! thanx!

### Always - Getting WA ... 336 - A node too Far

Posted: Fri May 09, 2003 9:07 am
Hi, I don't know why I always got WA. I have try all the possibilities for input.
and it woks. But I don't know why always got WA.
Any hint ?
my method : DFS.

Code: Select all

``Cut..``
Thanks.

Posted: Sat May 17, 2003 4:25 pm
well, i dont have any hint. usually DFS leads to TLE, as i got first. i cant compile your prog, since i use public computer. but i think you cannot use something like flood_fill. like this.
1 2
2 3
3 4
1 4
if we start from node 1 then node 4 will got TTL 3. but it should be 1.
anyway i used DFS and got TLE. after changing algo with something like DP then got AC at once

with love & light,

titid

Posted: Mon May 19, 2003 4:35 am
In my code, node 4 have TTL = 1.

if the input :
4
1 2
2 3
3 4
1 4
1 1
1 2
1 3
1 0
0 0

My output produce:
Case 1: 1 nodes not reachable from node 1 with TTL = 1.
Case 2: 0 nodes not reachable from node 1 with TTL = 2.
Case 3: 0 nodes not reachable from node 1 with TTL = 3.
Case 4: 3 nodes not reachable from node 1 with TTL = 0.

Huge Thanks
RS

Posted: Mon May 26, 2003 4:45 am
Thanks,
I've got AC when using BFS algorithms. I really don't know why DFS can't solve this problem...

Huge Thanks,
RS

Posted: Sun Jul 13, 2003 1:39 pm
My program gets WA when graph has cycle:
Example:

1
1 1
1 0
0 0
0

my program output:
"Case 1: 1 nodes not reachable from node 1 with TTL = 0."

i modifity this, and get ACC

### 336 -- why wa

Posted: Thu Sep 18, 2003 8:35 am
hello,
I am just start to implement the graph algorithms. I am trying to solve the problem 336. I have test it for all the possible case even for disjoin graph. but it is getting WA. Please anyone give me more input or tell me the tricks.

M H Rasel
CUET Old Sailor

Posted: Mon Sep 29, 2003 11:18 pm
i solved it using TTL-depth BFS.

just remember that the number of the node can be >n, something very big (but fits into long int ). if this is your problem, a linear search can pass the time limit :p

### Pls Help - 336

Posted: Thu Oct 16, 2003 8:54 am
Hi
I am trying to solve this problem But I am surprised that I cannot able to get accept this problem with my level best effort. To learn about this type of problem (BFS problem) I have collect the judge code also and compare with my code. But I donâ€™t found any difference with this two code. So please anyone help me to find the difference. Here is my code

[cpp]
#include<stdio.h>

#define MAX 35

#define INF 99999

#define WHITE 0
#define GRAY 1
#define BLACK 2

int nodelist[MAX],maxnode;
int color[MAX];
int d[MAX];

/**************************** Queue ******************/
int queue[MAX], front,rare;

void initqueue(void)
{
front = rare = 0;
}

int del(void)
{
return queue[rare++];
}

void insert(int i)
{
queue[front++] = i;
}

int isempty(void)
{
return (front==rare);
}
/**************************** End of Queue ******************/

void refresh(void)
{
register int i,j;
for(i=0;i<MAX;i++)
{

for(j=0;j<MAX;j++) // change new
}

maxnode = 0;

}

int find(int id) // OK!
{
register int i;

for(i= 0 ; i< maxnode; i++)
if(nodelist==id)
return i;

nodelist[maxnode] = id;
return maxnode++;
}
/**************************** Getting input ******************/
void input(int n)
{
register int i,x,y;
int u,v;

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

x = find(u);//
y = find(v);//

}
}
/**************************** End of Getting input ******************/

int bfs(int s,const int ttl)
{
int reach = 0,u,v;
register int i;

for(i=0;i<maxnode;i++)
{
color = WHITE;//ok!
d = INF;//ok!
}

color[s] = GRAY;
d[s] = 0; //

initqueue();// ok!
insert(s); // ok!
reach = 1;// ok!

while(!isempty())//ok!
{
u = del(); // ok!

if(d < ttl)
{
{
if(color[v] == WHITE) // ok!
{
reach++; //ok!
color[v] = GRAY;//ok!
d[v]= d+1;// ok!
insert(v);//ok!
}
// pre. 100 is here
}
}

color = BLACK; // 100
}
return reach;
}

main(void)
{
int caseno = 0 ,n,s,ttl,x,reach;

while(scanf("%d",&n)!=EOF)// funny
{
if(n==0)//
break;//

refresh();// maxnode = 0
input(n);

while(scanf("%d%d",&s,&ttl))
{
if(s==0 && ttl == 0)// funny
break;

x = find(s);//

reach = bfs(x,ttl);
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++caseno,maxnode - reach,s,ttl);
}
}
return 0;
}
[/cpp]

The judge code is the following
[cpp]

/* @JUDGE_ID: xxxxxxx 336 C++ */

/* Author: Reuber Guerra Duarte(reuber@dcc.ufmg.br) */

#include <stdio.h>
int m[30][30];
int n, pn;
int nodes[30];
int queue[30];
int v[30];

int search(int id)
{
int i;
for (i = 0; i < n; i++)
if (nodes == id)
return i;
for (i = 0; i <= n; i++)
{
m[n] = 0;
m[n] = 0;
}

nodes[n] = id;

return n++;
}

void visit(int start, int ttl)
{
int t, count, j;
tail = 0;
count = 1;
queue[tail++] = start;

for (j = 0; j < n; j++)
v[j] = -1;
v[start] = 0;

{

if (v[t] < ttl)
for (j = 0; j < n; j++)
if (v[j] < 0 && m[t][j])
{
v[j] = v[t] + 1;
queue[tail++] = j;
count++;
}
}

printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++pn, n - count, nodes[start], ttl);

}

int main()
{
int i, j, e1, e2;
while (1 == scanf("%d", &j))
{
if (j == 0)
break;
n = 0;
for (i = 1; i <= j; i++)
{
scanf("%d %d", &e1, &e2);
e1 = search(e1);
e2 = search(e2);
m[e1][e2] = 1;
m[e2][e1] = 1;
}

while (1)
{
scanf("%d %d", &e1, &e2);
if (e1 == 0 && e2 == 0)
break;
e1 = search(e1);
visit(e1, e2);
}
}
return 0;
}
[/cpp]

M H Rasel.
CUET OLD SAILOR

### 336:

Posted: Fri Oct 31, 2003 10:07 am
Any body willing to chk my code ?
Suman.

### 336: Output Limit Exceeded!!

Posted: Thu Nov 06, 2003 12:51 am
I'm trying to solve 336 and i'm having Output Limit Exceeded...
I think I should have a problem with I/O, can you help me??? Please!! I'me getting crazy!!!

[cpp]#include <iostream.h>
#include <map.h>
#include <stack.h>
//#include <queue.h>
#include <stdio.h>

using namespace std;

int visitar (int n0, int n, int max, bool ady [40][40]) {
int dist [40];
queue<int> q;

for (i=0; i < n; i++) dist =-1;
dist [n0]=0;
q.push (n0);
q.push (-1);
do {
v=q.front ();
q.pop ();
if (v<0) {
d++;
v=q.front ();
q.push (-1);
} else {
for (i=0; i < n; i++)
if (ady [v] && dist < 0) {
q.push (i);
dist = d+1;
}
}
} while (v>=0 && d <= max);

}

int main () {
int i,j,n,ultimo, p1, p2, c1, c2;
map<int,int> mapa;
map<int,int>::const_iterator it;
int cont=0;
do {
cin >> n;
if (!n) return 0;
if (!cin) return 0;

if (n < 0) while (true) ultimo++;
ultimo=0;
mapa.clear ();
for (i=0; i < n; i++)
for (j=0; j < n; j++)

for (i=0; i < n; i++) {
cin >> c1 >> c2;
if ((it=mapa.find (c1)) == mapa.end ()) {
p1=ultimo;
mapa [c1]=p1;
ultimo++;
} else p1=it->second;

if ((it=mapa.find (c2)) == mapa.end ()) {
p2=ultimo;
mapa [c2]=p2;
ultimo++;
} else p2=it->second;

}

//if (ultimo > 40) while (true) ultimo++;

int n0, ttl, nr;
do {
cin >> n0 >> ttl;
if (!cin) return 0;

if (!n0 && !ttl) break;
if ( (it=mapa.find (n0)) == mapa.end ()) nr = ultimo;
else nr=ultimo-visitar (mapa [n0],ultimo, ttl, ady);
printf ("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++cont,nr,n0,ttl);
} while (true);

} while (true);
}[/cpp]

### 336 A Node Too Far - What could be wrong?

Posted: Sat Dec 20, 2003 10:33 am
I'm attempting Q336 A Node Too Far, yet I'm getting WA >_<"

Well I must say I couldn't find anything wrong with my code... actually I've solved a great deal of BFS problems before....

So instead of posting my code here, I would like to ask if there's anything I need to take extra care in solving this task. Test cases are also welcomed. Thanks in advance.

P.S. Is the input file terminated by a case where NC = 0?