10199 - Tourist Guide

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Bunau Florin
New poster
Posts: 1
Joined: Wed Apr 04, 2007 3:48 pm
Contact:

Post by Bunau Florin » Wed Apr 04, 2007 4:05 pm

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

Post by ferng1021 » Fri Aug 10, 2007 8:37 pm

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!!

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Mon Mar 17, 2008 8:12 pm

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:

Post by mf » Tue Mar 18, 2008 2:12 pm

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.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Tue Mar 18, 2008 5:30 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by joy » Fri Mar 21, 2008 4:02 am

I cn't find where is the problem... It passes all the I/O in this forum...
plz help..

Code: Select all

ACC......  
:D
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....

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Fri Mar 21, 2008 6:26 am

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
Location: Dhaka, Bangladesh
Contact:

Post by joy » Tue Mar 25, 2008 4:03 am

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

Post by ani_mitr86 » Sat Jul 05, 2008 2:36 pm

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

Post by sijal » Fri Aug 15, 2008 9:07 pm

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

Post by stcheung » Thu Oct 09, 2008 8:01 am

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

Post by sijal » Fri Oct 10, 2008 1:03 pm

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

Post by ngchumin » Thu May 27, 2010 5:42 am

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

Post by roger12345 » Tue Feb 01, 2011 6:54 am

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

Post by helloneo » Tue Feb 01, 2011 6:16 pm

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

Remove you code after AC

Post Reply

Return to “Volume 101 (10100-10199)”