## 10199 - Tourist Guide

Moderator: Board moderators

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
I also got WA. My program passed all previous sample in/out s in this thread. Please help me to identify my problem. here is the code:
[c]#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define min(a, b) (a < b) ? a : b
#define MAXV 105
#define MAXE 5100

int adj[MAXV][MAXV], dfn[MAXV], L[MAXV], num, n;
int edges[MAXE][2], e;

char ara[MAXV][35];

int get_indx(char s[])
{
for(int i=1; i<=n; i++)
if(!strcmp(ara, s))
return i;
return 0;
}

void art(int u, int v)
{
int w;
dfn = num;
L = num;
num++;

for(w=1; w<=n; w++)
{
{
if(!dfn[w])
{
edges[e][0] = u;
edges[e++][1] = w;
art(w, u);
L = min(L, L[w]);
}
else if(w!=v)
L = min(L, dfn[w]);
}
}
}

int comp(const void *a, const void *b)
{
char *x = (char *)a;
char *y = (char *)b;
return strcmp(x, y);
}

void main()
{
char a[35], b[35], ans[MAXV][35];
int points[MAXV];
int i, j, count, u, v, root, r_count, map=0, m;

while(1==scanf("%d", &n) && n)
{
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++) adj[j] = 0;
dfn = 0;
}
for(i=1; i<=n; i++) scanf("%s", ara);
scanf("%d", &m);
while(m--)
{
scanf("%s%s", a, b);
i = get_indx(a);
j = get_indx(b);
}
e = 0;
num = 1;
art(1, 0);

for(i=1; i<=n; i++) points = 0;
root = 1;
r_count = 0;
count = 0;
for(i=0; i<e; i++)
{
u = edges[0];
if(u==root)
{
r_count++;
continue;
}
if(points) continue;
v = edges[1];
if( L[v] >= dfn)
{
count++;
points = 1;
}
}
if(r_count > 1)
{
count++;
points[root] = 1;
}
if(map) printf("\n");
printf("City map #%d: %d camera(s) found\n", ++map, count);

for(i=1, j=0; i<=n; i++)
if(points)
strcpy(ans[j++], ara[i]);
qsort((void *)ans, j, sizeof(ans[0]), comp);
for(i=0; i<count; i++) printf("%s\n", ans[i]);
}
}[/c]
( I have got 315 AC with almost same code )

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Can anyone tell me what is the output of the following input set...

Input:

Code: Select all

``````5
a
b
c
d
e
4
a b
b c
a d
d c
0``````
Thanks...
Ami ekhono shopno dekhi...
HomePage

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
output:

Code: Select all

``````City map #1: 0 camera(s) found
``````

indyman
New poster
Posts: 7
Joined: Thu Nov 30, 2006 12:36 pm
Can anybody help me out? I am getting WA even though I get correct answers for all examples posted on this topic. What is the program really supposed to do for disconnected graphs? Many people have asked this before on this topic, but it hasnt really been answered yet. I am just wondering if thats where I am doing something wrong.

If I am not doing anything wrong with disconnected graphs, are there any other gotchas besides the alphabetical order?

Also, I am having a trailing extra endl at the end since I use it to insert space between cases. Is that right? I tried both ways - with the extra endl and without - I got WA both times. I am bummed!

Here are the inputs & outputs (all compiled from prior posts under this topic) my code gives me:

Code: Select all

``````Input:
6
sugarloaf
maracana
copacabana
ipanema
lapa
7
ipanema copacabana
copacabana sugarloaf
ipanema sugarloaf
maracana lapa
sugarloaf maracana
5
guanabarabay
downtown
botanicgarden
colombo
sambodromo
4
guanabarabay sambodromo
downtown sambodromo
sambodromo botanicgarden
colombo sambodromo
6
a
b
d
c
e
f
7
a b
a d
d c
b d
c e
c f
e f
7
g
f
e
d
c
b
a
6
a b
b c
c d
d e
e f
f g
7
g
f
e
d
c
b
a
7
a b
b c
c d
d e
e f
f g
g a
7
g
f
e
d
c
b
a
5
b c
c d
d e
e f
f g
6
a
b
c
d
e
f
5
a b
a f
c d
c e
d e
5
a
b
c
d
e
4
a b
b c
a d
d c
0
``````

Code: Select all

``````Output:
City map #1: 1 camera(s) found
sugarloaf

City map #2: 1 camera(s) found
sambodromo

City map #3: 2 camera(s) found
c
d

City map #4: 5 camera(s) found
b
c
d
e
f

City map #5: 0 camera(s) found

City map #6: 1 camera(s) found
f

City map #7: 2 camera(s) found
a
c

City map #8: 0 camera(s) found

``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
My accepted code returns...

Output:

Code: Select all

``````City map #1: 1 camera(s) found
sugarloaf

City map #2: 1 camera(s) found
sambodromo

City map #3: 2 camera(s) found
c
d

City map #4: 5 camera(s) found
b
c
d
e
f

City map #5: 0 camera(s) found

City map #6: 4 camera(s) found
c
d
e
f

City map #7: 1 camera(s) found
a

City map #8: 0 camera(s) found``````
Dont worry about presentation. If your output format is not correct you will get accepted(presentation error).
And if the graph is disconnected just print the articulations from each connected subgrapth.
Hope these help.
Ami ekhono shopno dekhi...
HomePage

indyman
New poster
Posts: 7
Joined: Thu Nov 30, 2006 12:36 pm
Jan,

Thanks for the output from your accepted code. I fxed my code and am getting the same answers for this input as you posted. Still WA. Any ideas as to which test cases might help? I am bummed.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the cases...

Input:

Code: Select all

``````6
a
b
c
d
e
f
3
a f
b c
e d
6
a
b
c
d
e
f
6
a f
b c
e d
f e
a d
b d
6
x
y
z
a
b
c
0
6
x
y
z
a
b
c
7
x y
y z
z x
a b
b c
a c
a z
0``````
Output:

Code: Select all

``````City map #1: 0 camera(s) found

City map #2: 2 camera(s) found
b
d

City map #3: 0 camera(s) found

City map #4: 2 camera(s) found
a
z``````
Ami ekhono shopno dekhi...
HomePage

indyman
New poster
Posts: 7
Joined: Thu Nov 30, 2006 12:36 pm
Hi Jan,

My code passed the above test cases you posted:
This is the output:

Code: Select all

``````City map #1: 0 camera(s) found

City map #2: 2 camera(s) found
b
d

City map #3: 0 camera(s) found

City map #4: 2 camera(s) found
a
z

``````
This is my code... Hope you can help..

Code: Select all

``````Code Removed
``````
Hope you can help.... Thanks...
Last edited by indyman on Fri Dec 01, 2006 10:32 am, edited 1 time in total.

indyman
New poster
Posts: 7
Joined: Thu Nov 30, 2006 12:36 pm
Jan,

I think the following test case also might help me figure out whats wrong:

Input:

Code: Select all

``````6
a
b
c
d
e
f
4
a b
a f
c d
d e
0
``````
The output I get, is:

Code: Select all

``````City map #1: 1 camera(s) found
a

``````
Although, if you make the graph, its like this:

Code: Select all

``````b ------ a ------- f

c ------ d ------- e
``````
where there are two disjoint parts of the graph. Shouldnt the answer be

Code: Select all

``````City map #1: 2 camera(s) found
a
d
``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
My code returns

Code: Select all

``````City map #1: 2 camera(s) found
a
d``````
which is correct.
Ami ekhono shopno dekhi...
HomePage

indyman
New poster
Posts: 7
Joined: Thu Nov 30, 2006 12:36 pm
Just as I thought. Thanks man. If you get any insights from my code, please let me know. I am thinking theres something wrong with the way I compute my low[] in the function low2[].

Thanks.

indyman
New poster
Posts: 7
Joined: Thu Nov 30, 2006 12:36 pm
Jan,

Thank you very much for the test cases and advice. I figured out the error in my code. In my implementation of articulation points, I was calculating low using regular edges instead of the edges from the DFS tree. Doh! )

Thanks a lot once again!

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
I have no idea for which input my code fails..
I am getting WAs

Code: Select all

``````Removed after got Accepted
``````

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am