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

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

10199 - Tourist Guide

Post by junjieliang » Thu Dec 19, 2002 6:23 am

Is this problem finding articulation points? I'm doing that but I keep on getting WA :o

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse » Thu Jan 30, 2003 7:01 am

Yes.

The graph is possibly disconnected, so you may have to run the algorithm more than once.

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:

I am getting WA!

Post by ram » Wed Mar 19, 2003 9:20 am

I think I considered disconnected graph also, but still getting WA! Can anybody help. Here is the code

:cry:


[cpp]
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <map>
#include <iomanip>
#include <vector>
#include <fstream>

using namespace std;

typedef map<string,int> XX;
XX mapper;
typedef map<int,string> LL;
LL mapper2;
int field[100][100];
int color2[100];
int par[100][100];
int chld[100][100];
int dfnum[100],low[100];
int color[100];
int verts,eds;
int dfn;

void DFSer(int I){
int i,j,k;
color=1;
dfnum=low=dfn++;

for(i=0;i<verts;i++){
if(field==1&&color==0) {
chld=1;
par=1;
DFSer(i);
}
}
}

void solver(int I){

int i,j,k;
color2[I]=1;

for(i=0;i<verts;i++)
if(color2[i]==1&&field[I][i]==1) low[I]=min(low[I],dfnum[i]);

for(i=0;i<verts;i++){
if(color2[i]==0&&chld[I][i]==1)
solver(i);
}

for(i=0;i<verts;i++) if(color2[i]==0&&chld[I][i]==1&&low[i]<dfnum[i]) low[I]=min(low[I],low[i]);

color2[I]=0;
}


int main(){
int i,j,k,cases;
vector<int> res;
vector<string> finder;
bool flag;
string temp,temp2;
cases=0;
while(cin>>verts){
if(verts==0) break;
memset(field,0,sizeof(field));
memset(par,0,sizeof(par));
memset(chld,0,sizeof(chld));
for(i=0;i<verts;i++){
cin>>temp;
mapper[temp]=i;
mapper2[i]=temp;
}
cin>>eds;
for(i=0;i<eds;i++){
cin>>temp>>temp2;
j=mapper[temp];
k=mapper[temp2];
field[j][k]=1;
field[k][j]=1;
}
memset(dfnum,0,sizeof(dfnum));
memset(low,0,sizeof(low));
memset(color,0,sizeof(color));
memset(color2,0,sizeof(color2));
dfn=0;
res.clear();
finder.clear();
for(i=0;i<verts;i++){
if(color[i]==0){
DFSer(i);
solver(i);
k=0;
for(j=0;j<verts;j++) if(chld[i][j]==1) k++;
if(k>1) res.push_back(i);
for(k=i+1;k<verts;k++){
for(j=i+1;j<verts;j++){
if(chld[k][j]==1&&low[j]>=dfnum[k]){
chld[k][j]=0;
par[j][k]=0;
field[k][j]=0;
field[j][k]=0;
res.push_back(k);
break;
}
}
}
}
}
cases++;
if(cases>1) cout<<endl;
cout<<"City map #"<<cases<<": "<<res.size()<<" camera(s) found"<<endl;
for(i=0;i<res.size();i++) finder.push_back(mapper2[res[i]]);
sort(finder.begin(),finder.end());
for(i=0;i<finder.size();i++) cout<<finder[i]<<endl;

}
return 0;
}


[/cpp]


Thanx in advance

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Wed Aug 20, 2003 5:19 pm

please post some input-output
--
"Everything should be made simple, but not always simpler"

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

Post by carneiro » Sat Sep 13, 2003 3:30 am

Here's what you're looking for :

Code: Select all

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
6
a b
b c
c d
d e
e f
f a
0
and the *ACCEPTED* 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: 0 camera(s) found
Hope this would help !
[]s
Mauricio Oliveira Carneiro

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Sat Sep 13, 2003 2:17 pm

Thanks a million carneiro! I'd never find my mistake if not for your test case... I missed the part about alphabetical order!

Oh man... let's hope I don't make silly mistakes again... :oops:

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Sep 14, 2003 2:57 pm

Excuse me...

Wht should i do if the input graph is disconnected? Always output 0? :-?

p.s. my program can pass the i/o above perfectly. still, wa.....
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

Post by carneiro » Sun Sep 14, 2003 11:45 pm

if you handle the I/O above, then your program is handling correctly disconnected graphs, don't worry about that, your problem may be elsewhere ...
[]s
Mauricio Oliveira Carneiro

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Mon Sep 15, 2003 10:52 am

then could anyone plz give me some more test cases? Thx in advance. :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

WA

Post by erfan » Wed Nov 05, 2003 12:31 pm

I solve 10199 but still WA though all of I/O post in this page are ok.
here is my code without articulation point.
[cpp]

long search(char key[])
{
long i;
for(i=0;i<N;i++)

if(!strcmp(key,s1))return i;
return -1;
}
int main(void)
{
long i,m,x,y,p,kase=0;
freopen("10199.in","r",stdin);
while(scanf("%ld",&N)==1)
{
if(!N)break;
init();
if(kase)printf("\n");
for(i=0;i<N;i++)
scanf("%s",s1);
qsort((void *)s1, N, sizeof(s1[0]), sort_function);
scanf("%ld",&m);
for(i=0;i<m;i++)
{
scanf("%s %s",s,e);
x=search(s);
y=search(e);
mat[x][y]=1;
mat[y][x]=1;
}
p = findArtPoint();
printf("City map #%ld: %ld camera(s) found\n",++kase,p);
for(i=0;i<N;i++)
if(artV)
printf("%s\n",s1);
}
return 0;
}
[/cpp]
My Articulation point is AC for 315.
Plz can anyone help me...!!!

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Wed Nov 05, 2003 8:12 pm

You probably did not consider the case when the graph is not connected.
In 315,on the other hand, you are told that the graph is connected, that's why AC :-)

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

Post by erfan » Thu Nov 06, 2003 10:45 am

Yah, I repair for disconnected graph.But still WA
Please give me some test data(I/O).
I always getting big big WA...... :cry:

hijbul_ctg
New poster
Posts: 8
Joined: Sat Apr 19, 2003 5:41 pm
Contact:

KWAESH

Post by hijbul_ctg » Sat Nov 08, 2003 9:41 pm

NOT FOR 10199 BUT FOR MY FRIEND Er-FUN(PIAL)

WHAT DO YOU WANT ? .....................................
MONEY, FAME OR FRIEND(SPECIALLY GEL)

PIAL(ma :evil: )

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Nov 27, 2003 6:16 pm

carneiro wrote:if you handle the I/O above, then your program is handling correctly disconnected graphs, don't worry about that, your problem may be elsewhere ...
It's me again! :)

I've just got ACC in Q315... still... no luck on 10199... :( :( :(

Plz...... anyone plz help
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Fri Nov 28, 2003 12:21 pm

Acc-ed :D

My problem is really on "disconnected" graphs...

For those who're still stuck, try the following case:
6
a
b
c
d
e
f
5
a b
a f
c d
c e
d e
0
Output:
City map #1: 1 camera(s) found
a
Have fun ~~ :)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest