Page 1 of 9

336

Posted: Sat Oct 12, 2002 8:57 pm
by 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

Posted: Sat Oct 12, 2002 11:07 pm
by Ivan Golubev
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
by jpfarias
Just solved it...

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

Thanx anyway!!

Posted: Sun Jan 19, 2003 11:04 pm
by ei01036
I'm getting WA all the time... :roll: 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
by 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.

Posted: Sat May 17, 2003 4:25 pm
by 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

Posted: Mon May 19, 2003 4:35 am
by 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 :lol:

Posted: Mon May 26, 2003 4:45 am
by 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 :lol: :lol: :lol:

Posted: Sun Jul 13, 2003 1:39 pm
by 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 :)

336 -- why wa

Posted: Thu Sep 18, 2003 8:35 am
by 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

Posted: Mon Sep 29, 2003 11:18 pm
by 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

Pls Help - 336

Posted: Thu Oct 16, 2003 8:54 am
by 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

336:

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

336: Output Limit Exceeded!!

Posted: Thu Nov 06, 2003 12:51 am
by 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]

336 A Node Too Far - What could be wrong?

Posted: Sat Dec 20, 2003 10:33 am
by 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?