336 - A Node Too Far

[jpfarias]

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

[Ivan Golubev]

Input:
4
1 2 2 3 4 5 5 6
1 5 1 1 4 2 0 0
0

[jpfarias]

Just solved it...

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

Thanx anyway!!

[ei01036]

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!

[Red Scorpion]

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.

[titid_gede]

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

[Red Scorpion]

Thanks, for replying.
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

[Red Scorpion]

Thanks,
I've got AC when using BFS algorithms. I really don't know why DFS can't solve this problem...

Huge Thanks,
RS

[bigbit]

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

[Master]

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.

Thanks in advance

M H Rasel
CUET Old Sailor

[playerX]

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

[Master]

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 adjlist[MAX][MAX];
int adjnum[MAX];
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++)
{
adjnum = 0;

for(j=0;j<MAX;j++) // change new
adjlist[j]=0;// 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);//

adjlist[x][adjnum[x]++] = y;// Adjacency list????
adjlist[y][adjnum[y]++] = x;// Adjacency list????
}
}
/**************************** 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)
{
for(i=0;i<adjnum;i++)
{
v = adjlist;
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 tail, head;
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;
head = 0;
count = 1;
queue[tail++] = start;

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

while (tail != head)
{

t = queue[head++];
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]


Thanks in advance
M H Rasel.
CUET OLD SAILOR

[sumankar]

Any body willing to chk my code ?
Suman.

[Cucu]

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 i,j,k, visitados=0, d=0,v;
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 {
visitados++;
for (i=0; i < n; i++)
if (ady [v] && dist < 0) {
q.push (i);
dist = d+1;
}
}
} while (v>=0 && d <= max);

return visitados;
}

int main () {
int i,j,n,ultimo, p1, p2, c1, c2;
bool ady [40][40];
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++)
ady [j]=false;

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;

ady [p1][p2]=true;
ady [p2][p1]=true;
}

//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]

[Observer]

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?