Page 1 of 3

10959 - The Party, Part I

Posted: Sun Nov 13, 2005 10:30 am
by Wei-Ming Chen
I wrote 10959 and got WA.....
Can someone give me some I/O?
thanks...

Posted: Sun Nov 13, 2005 4:48 pm
by polone

Code: Select all

3 3
0 1
1 2
0 2

Code: Select all

1
1

Posted: Sun Nov 13, 2005 8:37 pm
by Soarer
Hi, I got WA too, can anyone give some more complicated inputs? Thanks.

Posted: Mon Nov 14, 2005 7:20 am
by Wei-Ming Chen
Can you give me more output?
My code run this output is right

Posted: Mon Nov 14, 2005 1:02 pm
by polone
Maybe you can post your code :D

Posted: Mon Nov 14, 2005 2:36 pm
by Wei-Ming Chen
#include <stdio.h>
int main()
{
return 0;
}

Posted: Mon Nov 14, 2005 3:08 pm
by misof
First, this line: printf("%d %d %d %d %d %d\n",a[1],a[2],a[3],a[4],a[5],a[6]);
is at least strange and clearly doesn't belong into the final version of your code.

Second, the algorithm is wrong.
Consider the following input:

Code: Select all

1

3 2
1 2
0 1
Here the correct output is

Code: Select all

1
2

Posted: Mon Nov 14, 2005 3:11 pm
by Wei-Ming Chen
Oh~ That line is check code. I will delete when I submit it.
And why the outputs are 1 & 2
I thought it was 1 & (can't wrote it)

Posted: Mon Nov 14, 2005 3:36 pm
by misof
Wei-Ming Chen wrote:Oh~ That line is check code. I will delete when I submit it.
And why the outputs are 1 & 2
I thought it was 1 & (can't wrote it)
The order of the dances doesn't matter. Even if 2 danced with 1 before 1 danced with Don Guilianni, the D. G. number of 2 is still 2.

Posted: Mon Nov 14, 2005 4:25 pm
by Wei-Ming Chen
I thought you are right.
I changed my code and got AC
Thank you

Posted: Mon Nov 14, 2005 8:18 pm
by Soarer
Can anyone check it for me? Thanks.

#include<iostream>
#include<math.h>
using namespace std;

int main(){
int num_of_cases, loop = 1;
cin >> num_of_cases;
while(loop <= num_of_cases){

int num_of_people;
long num_of_dance, loop_2 = 1;
cin >> num_of_people >> num_of_dance;

int danced[num_of_people][num_of_people], number[num_of_people];

//initialization
for(int n = 0; n < num_of_people; n++){
number[n] = num_of_people;
}
number[0] = 0;

while(loop_2 <= num_of_dance){
int part_1, part_2;
cin >> part_1 >> part_2;

danced[part_1][part_2] = 1;
danced[part_2][part_1] = 1;

loop_2 ++ ;
}
for(int j = 0; j < num_of_people; j++){
for(int k = 0; k < num_of_people; k++){
if(number[k] == j){
for(int m = 0; m < num_of_people; m++){
if(number[m] > j && danced[k][m] == 1){
number[m] = j+1;
}
}
}
}
}

for(int k = 1; k < num_of_people; k++){
cout << number[k] << endl;
}

loop ++ ;
}
return 0;
}

Posted: Fri Nov 18, 2005 9:37 pm
by ayon
believe it or not, this problem is nothing but bfs; better use bfs, that will make your life easier...

Posted: Sat Nov 19, 2005 9:14 am
by Soarer
ayon wrote:believe it or not, this problem is nothing but bfs; better use bfs, that will make your life easier...
What is bf?

Posted: Sat Nov 19, 2005 9:44 am
by Observer
Soarer wrote:What is bf?
I guess it's not "bf", but "bfs" (Breadth First Search). :wink:

Posted: Sat Nov 19, 2005 11:23 am
by ayon
did i write bf? i think it's bfs(breadth first search), not bf(boyfriend).