10009 - All Roads Lead Where?

[turuthok]

Razib, I tried to copy-paste your code and ran the sample input. Funny that I just got blank-lines as output ...

I used gcc ...

-turuthok-

[razibcse]

thanx man for ur help...
actually my word size was too small...so I was getting WA..

I fixed it & got AC..

thanx again for ur assistance

[amir2099]

Ok.
The problem clearly states this:

A city will never be paired with itself in a query.

So I wrote a little program to see if the judge abides by this rule:

[cpp]
#include <iostream>
#include <string>

using namespace std;

bool connect[50][50];

int main()
{
int M,N;
cin >> M >> N;

string s1,s2;
int c1,c2;
for (int i=0; i < M; i++)
{
cin >> s1 >> s2;
c1=s1[0]-'A'; c2=s2[0]-'A';
connect[c1][c2]=connect[c2][c1]=true;
}

for (int i=0; i < N; i++)
{
cin >> s1 >> s2;
c1=s1[0]-'A'; c2=s2[0]-'A';
if (c1 == c2) int x=1/0;
}

return 0;
}
[/cpp]

And well, guess what!
I get a run time error.
meaning c1 == c2 when it obviously shouldn't.

Note to judges: If you can't insure the input is correct atleast provide it for us, as my time is more precious than wasted on crap like this.

[amir2099]

well, no one seems to want to reply to my message so i'll get to a more practical issue at hand:

how am i supposed to handle the case where c1 == c2 ? what am i to output.

I'm also curious as to why this program may have different answers, i.e. why is the checkmark blue? i did a little sketching and there can only be one shortest path in tree. could someone please provide me with a counter example. or reply.

[the LA-Z-BOy]

this problem is a multiple input problem...that's why it's marked with blue tick...
http://acm.uva.es/problemset/minput.html
check it and tell us if you got further problem...
Greetings

[amir2099]

Thanks a lot. I had yellow and blue confused. I got AC

[playerX]

Hi ppl, I'm going mad with this problem...
Could anyone please tell me what's wrong?

[c]I erased my code because it's only mistake was that I didn't reset the array to handle multiple input...[/c]

Thanks in advance.

[wonderboy]

Hello everyone,
I don't know why I keep getting a "Runtime Time Error" for this problem. OJ says there's an invalid memory reference. My program handles multiple input and if you see the code, you will notice that I have declared bigger arrays than required (actually needed of size 27) just to stay on the safe side. I have used Floyd-Warshall's algo. Please can anyone check my program with some input and help me in finding the bug. I have seen it a hundred times and can't figure it out . Thanks in advance for all the help.

Cheers!!!

Code: Select all

Deleted after getting AC. Didn't handle multiple input properly and also underestimated the city names length.

[Towhid]

This problem has a astonishing idea. It has very very large city name. I can not figure out but of course more than 40000 chars. I got ac after resizing my array with 100000. U can try it. But the idea of the problemsetter is just annoying I think.

[wonderboy]

Thanx Towhid for the help. Phew!! Finally got the AC. Actually, I had done two mistakes : First, my program didn't handle multiple inputs properly. I hadn't read the minput.html page properly. Then the mistake you had pointed out. I also had to use arrays of 100000 characters. I completely agree with you that this kind of input is very annoying. There's no point in testing the programming skills with such things. Anyway, I am relieved now.

[jambon_vn]

Can anyone point out my mistake? Thank.

Code: Select all

#include <iostream>
#include <string>

using namespace std;

long Num, M, N, numB, numC;
int A[27], B[27], C[27];

int main()
{
	cin >> Num;
	for (long k = 1; k <= Num; k++)
	{
		cin >> M >> N;

		long i;

		for (i = 1; i <= M; i++)
		{
			string city1, city2;
			cin >> city1 >> city2;
			A[city2[0] - 'A'] = city1[0] - 'A';
		}

		for (i = 1; i <= N; i++)
		{
			string city1, city2;
			cin >> city1 >> city2;
			long S = city1[0] - 'A';
			long F = city2[0] - 'A';
				
			long des = 'R' - 'A';

			numB = 0;
			while (S != des) 
			{
				B[++numB] = S;
				S = A[S];
			}

			numC = 0;
			while (F != des)
			{
				C[++numC] = F;
				F = A[F];
			}

			while (B[numB] == C[numC]) 
			{
				des = B[numB];
				numB--;
				numC--;
			}

			long j;
			for (j = 1; j <= numB; j++) cout << (char) (B[j] + 'A');
			cout << (char) (des + 'A');
			for (j = numC; j >= 1; j--) cout << (char) (C[j] + 'A');
			cout << endl;
		}

		if (k < Num) cout << endl;
	}
	return 0;
}

[Yile]

I know the city name is very long. So I just read the first letter of each name and skip the other letters. But still the Runtime Error (SIGSEGV)

Code: Select all

int case,m,n;
char city1,city2,c;
scanf("%d",&case);
while(case-->0){
  scanf("%d %d",&m,&n);
  c=getchar();/*eat the '\n'*/
  while(m-->0){
    city1=getchar();
    while(c!=' ')/*skip letters until the space*/
      c=getchar();
    city2=getchar();
    while(c!='\n')/*skip letters until the '\n'*/
      c=getchar();}
  while(n-->0){
    ...../*the same as the process of the loop of m*/}}

[mf]

My AC program assumes city's name is at most 1024 characters, so there's no need to read input by character.

[Yile]

Thanks, I've found the bug of my program and got AC. The length of the name doesn't cause the bug as you expect. Thank you again.

[Fali]

Here is my code, i