Page 3 of 4
Posted: Wed Apr 04, 2007 4:05 pm
by 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?
Posted: Fri Aug 10, 2007 8:37 pm
by 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!!
Posted: Mon Mar 17, 2008 8:12 pm
by 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!
Posted: Tue Mar 18, 2008 2:12 pm
by mf
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.
Posted: Tue Mar 18, 2008 5:30 pm
by andmej
Thanks mf! I'm going to read that part of the book and see what can I learn.
Posted: Fri Mar 21, 2008 4:02 am
by joy
I cn't find where is the problem... It passes all the I/O in this forum...
plz help..
Posted: Fri Mar 21, 2008 6:26 am
by andmej
Hello
joy.
Take a look at line 99 of your code:
The judge is expecting your program to get input from the standard input and not from file in.txt.
Have fun!
Posted: Tue Mar 25, 2008 4:03 am
by joy
thankss
andmej ...
I was sooo....
Re: 10199 - Tourist Guide
Posted: Sat Jul 05, 2008 2:36 pm
by 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.
Re: 10199 - Tourist Guide
Posted: Fri Aug 15, 2008 9:07 pm
by 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 ;
}
Re: 10199 - Tourist Guide
Posted: Thu Oct 09, 2008 8:01 am
by 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
Re: 10199 - Tourist Guide
Posted: Fri Oct 10, 2008 1:03 pm
by sijal
tnx sunny it helps me a lot !
Re: 10199 - Tourist Guide
Posted: Thu May 27, 2010 5:42 am
by 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!
Re: 10199 - Tourist Guide
Posted: Tue Feb 01, 2011 6:54 am
by roger12345
I passed all the inputs before
Can anybody help me out please?
Re: 10199 - Tourist Guide
Posted: Tue Feb 01, 2011 6:16 pm
by helloneo
Your code is printing an extra '\n' after the last case..
Remove you code after AC