10199 - Tourist Guide
Moderator: Board moderators
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(adj[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);
adj[j] = adj[j] = 1;
}
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 )
[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(adj[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);
adj[j] = adj[j] = 1;
}
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 )
Can anyone tell me what is the output of the following input set...
Input:
Thanks...
Input:
Code: Select all
5
a
b
c
d
e
4
a b
b c
a d
d c
0
Ami ekhono shopno dekhi...
HomePage
HomePage
output:
Nothing helpful. So I guess the error lies in your algorithm.
Code: Select all
City map #1: 0 camera(s) found
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:
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
corcovado
lapa
7
ipanema copacabana
copacabana sugarloaf
ipanema sugarloaf
maracana lapa
sugarloaf maracana
corcovado sugarloaf
lapa corcovado
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
My accepted code returns...
Output:
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.
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
And if the graph is disconnected just print the articulations from each connected subgrapth.
Hope these help.
Ami ekhono shopno dekhi...
HomePage
HomePage
Try the cases...
Input:
Output:
Hope these help. If your code passes, post your code.
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
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
HomePage
Hi Jan,
My code passed the above test cases you posted:
This is the output:
This is my code... Hope you can help..
Hope you can help.... Thanks...
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
Code: Select all
Code Removed
Last edited by indyman on Fri Dec 01, 2006 10:32 am, edited 1 time in total.
Jan,
I think the following test case also might help me figure out whats wrong:
Input:
The output I get, is:
Although, if you make the graph, its like this:
where there are two disjoint parts of the graph. Shouldnt the answer be
What does your code give?
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
Code: Select all
City map #1: 1 camera(s) found
a
Code: Select all
b ------ a ------- f
c ------ d ------- e
Code: Select all
City map #1: 2 camera(s) found
a
d
My code returns
which is correct.
Code: Select all
City map #1: 2 camera(s) found
a
d
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
I have no idea for which input my code fails..
I am getting WAs
I am getting WAs
Code: Select all
Removed after got Accepted
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
-
- New poster
- Posts: 1
- Joined: Fri Mar 02, 2007 10:26 pm