## 10199 - Tourist Guide

Moderator: Board moderators

Bunau Florin
New poster
Posts: 1
Joined: Wed Apr 04, 2007 3:48 pm
Contact:
Hi,
I have tried all inputs in this thread, and my solution returns corectly all of them. I have no ideea why do i get WA. Are there any trick cases?, What corner cases have you found?

some IO :

Code: Select all

``````7
a
b
c
d
e
f
g
7
a b
c b
d b
e f
f d
e g
f g
7
a
b
c
d
e
f
g
7
a b
c b
d b
e d
f d
g e
g f
0
``````
mine returns :

Code: Select all

``````City map #1: 3 camera(s) found
b
d
f

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

``````
Any ideeas why i get WA?, what was the cases yours didn't pass?

ferng1021
New poster
Posts: 9
Joined: Thu Feb 23, 2006 5:09 pm
Location: Taipei, Taiwan
I got same output as yours, Bunau.
And I also have no idea why getting WA.
Can any body help me and give some more I/O?

Thanks!!

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia
Hello, I'm getting Time Limit Exceeded in this problem. My algorithm is naive. What I simply do is try to remove each vertex in each connected component of the graph and check how many nodes are reachable (by DFS) without the removed node. If this node is less than the nodes reachable with the removed vertex, then it is an articulation point.

I think it is possible to determine if a point is an articulation point with a single graph traversal using DFS. However, I can't figure out how yet.

Can you give me a clue on how can I pass the time limit?

Thanks!
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
andmej wrote:I think it is possible to determine if a point is an articulation point with a single graph traversal using DFS. However, I can't figure out how yet.
'Articulation points' and 'DFS' are good enough search terms for google ;)

Also check problem 22-2 in CLRS (link to this problem in 1st edition); it doesn't describe the algorithm, but gives enough hints for you to do it yourself.

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia
Thanks mf! I'm going to read that part of the book and see what can I learn.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Contact:
I cn't find where is the problem... It passes all the I/O in this forum...
plz help..

Code: Select all

``````ACC......
``````
Last edited by joy on Tue Mar 25, 2008 4:03 am, edited 1 time in total.
form kisui na ... class tai asol....
iF U hv d class u get the form....

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia
Hello joy.

Take a look at line 99 of your code:

Code: Select all

``freopen("in.txt", "r", stdin);``
The judge is expecting your program to get input from the standard input and not from file in.txt.

Have fun!
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Contact:
thankss andmej ...
I was sooo....
form kisui na ... class tai asol....
iF U hv d class u get the form....

ani_mitr86
New poster
Posts: 20
Joined: Mon May 28, 2007 4:36 pm
Location: India

### Re: 10199 - Tourist Guide

Code: Select all

``````#include<cstdio>
#include<map>
#include<vector>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
//#include<conio.h>

void articulation_point_visit
(vector<int> *list, int* d, int* low, int* child_cnt, int n, int& time){
low[n]=d[n]=time++;
int l=list[n].size();
for(int v, i=0; i<l; i++){
v=list[n][i];
if(d[v]==0){
child_cnt[n]++;
articulation_point_visit(list, d, low, child_cnt, v, time);
low[n]<?=low[v];
}
else low[n]<?=d[v];
}
return;
}

vector<int> articulation_point(vector<int> *list, int sz){
bool root[sz+1];
int d[sz+1], low[sz+1], child_cnt[sz+1], time=1, l;
for(int i=1; i<=sz; i++){ root[i]=false; d[i]=0; child_cnt[i]=0;}
vector<int> points;

for(int i=1; i<=sz; i++) if(d[i]==0){
root[i]=true;
articulation_point_visit(list, d, low, child_cnt, i, time);
}
for(int i=1; i<=sz; i++){
if(root[i]&&(child_cnt[i]>1)) points.push_back(i);
if(!root[i]){
l=list[i].size();
for(int j=0; j<l; j++) if(d[i]<=low[list[i][j]]){ points.push_back(i); break;}
}
}

return points;
}

int main(){
//freopen("input.txt", "r", stdin);
int n, r, cnt=1;
string str, u, v;
map<string, int> m;
map<int, string> mi;
vector<string> vec;
vector<int> points;
while(1){
scanf("%d", &n);
if(n==0) break;
if(cnt>1) printf("\n");
m.clear(); mi.clear(); vec.clear();
for(int c=1, i=0; i<n; i++, c++){
cin>>str;
m[str]=c; mi[c]=str;
}
scanf("%d", &r);
vector<int> list[n+1];
for(int x, y, i=0; i<r; i++){
cin>>u>>v;
x=m[u]; y=m[v];
list[x].push_back(y);
list[y].push_back(x);
}
points=articulation_point(list, n);
printf("City map #%d: %d camera(s) found\n", cnt++, points.size());
for(vector<int>::iterator it=points.begin(); it!=points.end(); it++)
vec.push_back(mi[*it]);
sort(vec.begin(), vec.end());
for(vector<string>::iterator it=vec.begin(); it!=vec.end(); it++) cout<<*it<<endl;
}
//getch();
return 0;
}
``````
Can anybody help me out? I am continuously getting WA.

sijal
New poster
Posts: 9
Joined: Fri Jul 18, 2008 12:10 pm
Location: Iran-shiraz
Contact:

### Re: 10199 - Tourist Guide

can anybody help me , my program passes all the inputs in this thread .

#include<iostream>
#include<list>
#include<map>
#include<string>
#include<cstdlib>
using namespace std ;
#define V 101
typedef list<int> lis ;
int Dis[V] ;
int Min[V] ;
int disco ;
list<int> Tree[V] ; // childs of each vertex
int Parent[V] ; // parents
void dfs( lis graph[] , int current)
{
while( graph[current].size() > 0)
{
int n = graph[current].front() ;
graph[current].pop_front();
if( Dis[n] == -1 )
{
Dis[n] = Dis[current] + 1 ;
disco++ ;
Tree[current].push_back(n) ;
Parent[n] = current ;
dfs(graph , n) ;
}
}
}
int cmp( const void * s , const void * f )
{
const char **a = (const char **)s;
const char **b = (const char **)f;
return strcmp(*a, *b);
}
int main()
{
list<int> graph[V] ;// adjancy list representation
list<int> graph2[V] ;
disco = 0 ;
char** array = new char*[V] ;
int discovery = 0 ;
map<string , int> mamap ;
int city , pathes ;
for( int i = 0 ; i < V ; i++ )
{
array = new char[32] ;
}
char * first = new char [32] ;
char * second = new char [32] ;
int citymap = 0 ;
bool flag = false ;
while ( true )
{
scanf("%d" , &city ) ;
if( city == 0 )
{
return 0;
}
++citymap ;
mamap.clear() ;
for( int i = 0 ; i < city ; i++ )
{
scanf("%s" , array ) ;
//mamap[array] = i ;
Tree.clear() ;
}
int mm = 10 ;
qsort( array , city , sizeof(char*) , cmp ) ;
for( int i = 0 ; i < city ; i++ )
{
mamap[array] = i ;
}
scanf("%d" , &pathes ) ;
for( int i = 0 ; i < pathes ;i++)
{
scanf("%s %s" , first , second ) ;
graph[mamap[first]].push_back( mamap[second] ) ;
graph[mamap[second]].push_back( mamap[first] ) ;
}
for( int i = 0 ; i < city ; i++ )
{
Dis = Min = -1 ;
graph2 = graph ;
}
//DFS => build tree
for( int i = 0 ; i < city ; i++ )
{
if( graph.size() > 0 )
{
Parent[i] = -1 ;
Dis[i] = disco ;
Min[i] = disco ;
disco++ ;
dfs( graph , i ) ;
}
}
// filling DPTABLE
for( int i = 0 ; i < city ; i++ )
{
Min[i] = Dis[i] ;
}
for( int i = 0 ; i < city ; i++ )
{
for( list<int>::iterator it = graph2[i].begin() ; it != graph2[i].end() ; ++it )
{
if( Parent[*it] == i )
continue ;
int curr = Parent[*it] ;
if( Min[*it] > Dis[i] )
{
Min[*it] = Dis[i] ;
}
while( curr != -1 )
{
if( Min[curr] > Dis[i] )
{
Min[curr] = Dis[i] ;
}
curr = Parent[curr] ;
}

}
}
int res = 0 ;
int * arr = new int[101] ;
for( int i = 0 ; i < city ; i++ )
{
if( Parent[i] == -1 )
{
if( Tree[i].size() > 1 )
{
//printf("%d\n" , i ) ;
arr[res++] = i;
}
}
else
{
bool hast = false ;
for( list<int>::iterator pit = graph2[i].begin() ; pit != graph2[i].end() ; ++pit )
{
if( Min[*pit]>= Dis[i] )
{
hast = true ;
break ;
}
}
if( hast )
{
//printf("%d\n" , i ) ;
arr[res++] = i;
}

}
}
//
if( flag )
{
printf("\nCity map #%d: %d camera(s) found\n" , citymap , res ) ;
}
else
{
printf("City map #%d: %d camera(s) found\n" , citymap , res ) ;
}
for( int i = 0 ; i < res ; i++ )
{
printf("%s\n" , array[arr[i]] ) ;
}
flag = true ;

}

return 0 ;
}
Learn to swim.

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### Re: 10199 - Tourist Guide

After getting WA repeatedly despite having the same output as all the ones in this thread, I came up with the following input for which I finally got the wrong answer. So maybe it can help some of you. The answer should be "City map #1: 0 camera(s) found"...

6
a
b
c
d
e
f
7
a b
b c
c d
d a
e b
c f
e f
0

sijal
New poster
Posts: 9
Joined: Fri Jul 18, 2008 12:10 pm
Location: Iran-shiraz
Contact:

### Re: 10199 - Tourist Guide

tnx sunny it helps me a lot !
Learn to swim.

ngchumin
New poster
Posts: 8
Joined: Sun Jun 16, 2002 11:18 am

### Re: 10199 - Tourist Guide

Hi,

I have passed all the inputs in this thread but still getting WA. anyone with any more tricky cases?

Thanks alot for any help!

roger12345
New poster
Posts: 3
Joined: Tue Feb 01, 2011 5:40 am

### Re: 10199 - Tourist Guide

I passed all the inputs before
Can anybody help me out please?

Code: Select all

``Removed after A.C.``
Last edited by roger12345 on Fri Feb 11, 2011 9:35 am, edited 5 times in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 10199 - Tourist Guide

Your code is printing an extra '\n' after the last case..

Remove you code after AC