10199 - Tourist Guide

[Bunau Florin]

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]

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]

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!

[mf]

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]

Thanks mf! I'm going to read that part of the book and see what can I learn.

[joy]

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

Code: Select all

ACC......  

[andmej]

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!

[joy]

thankss andmej ...
I was sooo....

[ani_mitr86]

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]

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 ;
}

[stcheung]

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]

tnx sunny it helps me a lot !

[ngchumin]

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]

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

Code: Select all

Removed after A.C.

[helloneo]

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

Remove you code after AC