336 - A Node Too Far
Moderator: Board moderators
336
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
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
-
- Experienced poster
- Posts: 167
- Joined: Fri Oct 19, 2001 2:00 am
- Location: Saint Petersburg, Russia
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
Always - Getting WA ... 336 - A node too Far
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.
Thanks.
and it woks. But I don't know why always got WA.
Any hint ?
my method : DFS.
Code: Select all
Cut..
Last edited by Red Scorpion on Mon May 26, 2003 4:41 am, edited 1 time in total.
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
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![:)](./images/smilies/icon_smile.gif)
with love & light,
titid
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
![:)](./images/smilies/icon_smile.gif)
with love & light,
titid
Kalo mau kaya, buat apa sekolah?
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
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:](./images/smilies/icon_lol.gif)
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:](./images/smilies/icon_lol.gif)
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
-
- Learning poster
- Posts: 82
- Joined: Thu Oct 10, 2002 1:15 pm
- Location: St. Johns, Canada
- Contact:
336 -- why wa
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
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
-
- Learning poster
- Posts: 82
- Joined: Thu Oct 10, 2002 1:15 pm
- Location: St. Johns, Canada
- Contact:
Pls Help - 336
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
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:
Any body willing to chk my code ?
Suman.
Suman.
336: Output Limit Exceeded!!
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]
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?
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?
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?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org