## 567 - Risk

Moderator: Board moderators

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
To alamgir

-> You should print a blank line after each case
-> Remove the line
freopen("output.txt","w", stdout);
freopen("input.txt","r", stdin);

Thanks
Keep posting
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
thanks a lot man.
i got AC by using BFS.
''I want to be most laziest person in the world''

theharshest
New poster
Posts: 20
Joined: Thu Jan 17, 2008 10:47 pm
Location: India

### Re: 567 (Risk) - Wrong Answer

Code: Select all

``````#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;

int main()
{
int g[25][25][25];
int t,m,c=0,x,y,n;

while(1)
{
c++;
for(int i=0;i<20;i++)
for(int j=0;j<20;j++)
{
if(i!=j)
g[0][i][j]=1000;
else
g[0][i][j]=0;
}

for(int i=0;i<19;i++)
{

if(cin>>t)
for(int j=0;j<t;j++)
{
cin>>m;
g[0][i][m-1]=1;
g[0][m-1][i]=1;
}
else
goto end;
}

for(int k=1;k<20;k++)
for(int i=0;i<20;i++)
for(int j=0;j<20;j++)
g[k][i][j]=min(g[k-1][i][j] , g[k-1][i][k] + g[k-1][k][j]);

cin>>n;

cout<<"Test Set #"<<c<<endl;
for(int i=0;i<n;i++)
{
cin>>x>>y;
printf("%2d to %2d: %d\n",x,y,g[19][x-1][y-1]);
}

cout<<endl;

}
end:;

}
``````
"if u r goin thru hell, keep goin"

dodouuu
New poster
Posts: 9
Joined: Tue Mar 24, 2009 7:50 pm

### Re: 567 (Risk) - Wrong Answer

can anyone give me some directions?

my code:

#include <stdio.h>
#include <limits.h>

#define MAX_L 20 /* max lands */

long long int min(long long int a,long long int b) {
if( a > b ) return b;
else return a;
}

int main() {
/*freopen("in", "r", stdin);
freopen("out", "w", stdout); //*/

long long int lands[MAX_L][MAX_L];
int i, j, k, l;
int counter = 0;

/* initialize */
for(i=MAX_L-1; i>=0; i--)
for(j=MAX_L-1; j>=0; j--)
lands[j] = LONG_MAX;

while( scanf("%d", &k)!=EOF ) {
for(j=k-1; j>=0; j--) {
scanf("%d", &l);
lands[0][l-1] = lands[l-1][0] = 1;
}
for(i=MAX_L-3; i>=0; i--) {
scanf("%d", &k);
for(j=k-1; j>=0; j--) {
scanf("%d", &l);
lands[MAX_L-2-i][l-1] = lands[l-1][MAX_L-2-i] = 1;
}
}

/* Floyd-Warshall */
for(k=MAX_L-1; k>=0; k--)
for(i=MAX_L-1; i>=0; i--)
for(j=MAX_L-1; j>=0; j--)
lands[j] = min( lands[j], lands[k]+lands[k][j] );
/* Floyd-Warshall */

if(counter > 0)
printf("\n");
printf("Test Set #%d\n", ++counter);
scanf("%d", &k);
for(i=k-1; i>=0; i--) {
scanf("%d%d", &j, &l);
printf("%2d to %2d: %lld\n", j, l, lands[j-1][l-1]);
}

/* initialize */
for(i=MAX_L-1; i>=0; i--)
for(j=MAX_L-1; j>=0; j--)
lands[j] = LONG_MAX;
}

return 0;
}

dodouuu
New poster
Posts: 9
Joined: Tue Mar 24, 2009 7:50 pm

### Re: 567 (Risk) - Wrong Answer

AC.........

Clark85
New poster
Posts: 1
Joined: Thu May 21, 2009 11:22 am

### Re: 567 (Risk) - Wrong Answer

Excuse me dodouuu...could tell me how did you make your code accepted? Thanks in advance.

iqbal csedu
New poster
Posts: 3
Joined: Sun Jun 13, 2010 9:37 pm
Contact:

### Re: 567 (Risk) - Wrong Answer

I cant understand why i am getting worng answer.is there any one to help me
I used simple bfs.

Code: Select all

``````#include<cstdio>
#include<queue>
using namespace std;

int g[21][21],d[21],seen[21];
int main()
{
//freopen("output.txt","w",stdout);

queue<int> q;

int count=0,i,e,num,k,j,tc,s,u,v,source,destination;

while(1)
{
for(i=0;i<=20;i++)
for(j=0;j<20;j++)
g[i][j]=0;
for(i=1;i<=19;i++)
{
e=scanf("%d",&num);
if(e!=1)
return 0;

for(j=1;j<=num;j++)
{
scanf("%d",&k);
g[i][k]=1;
g[k][i]=1;
}
}

count++;

scanf("%d",&tc);

printf("Test Set #%d\n",count);

for(i=1;i<=tc;i++)
{
for(j=0;j<=20;j++)
{
d[j]=0;
seen[j]=0;
}

scanf("%d %d",&source,&destination);
s=source;
d[s]=0;
seen[s]=1;
q.push(s);

while(q.empty()==0)
{
u=q.front();
q.pop();
for(v=1;v<=20;v++)
{
if(g[u][v]==1 && seen[v]==0)
{
d[v]=d[u]+1;
seen[v]=1;
q.push(v);
}
}
if(seen[destination]==1)
{
printf("%2d to %2d: %d\n",source,destination,d[destination]);
while(q.empty()==0)
q.pop();
break;
}
}
}
printf("\n");
}
return 0;
}``````
I dream a dream...but my dream is not coming true(still now).

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### Re: 567 (Risk) - Wrong Answer

check the following input (Sample input in the problem twice)
1 3
2 3 4
3 4 5 6
1 6
1 7
2 12 13
1 8
2 9 10
1 11
1 11
2 12 17
1 14
2 14 15
2 15 16
1 16
1 19
2 18 19
1 20
1 20
5
1 20
2 9
19 5
18 19
16 20
4 2 3 5 6
1 4
3 4 10 5
5 10 11 12 19 18
2 6 7
2 7 8
2 9 10
1 9
1 10
2 11 14
3 12 13 14
3 18 17 13
4 14 15 16 17
0
0
0
2 18 20
1 19
1 20
6
1 20
8 20
15 16
11 4
7 13
2 16
1 3
2 3 4
3 4 5 6
1 6
1 7
2 12 13
1 8
2 9 10
1 11
1 11
2 12 17
1 14
2 14 15
2 15 16
1 16
1 19
2 18 19
1 20
1 20
5
1 20
2 9
19 5
18 19
16 20
4 2 3 5 6
1 4
3 4 10 5
5 10 11 12 19 18
2 6 7
2 7 8
2 9 10
1 9
1 10
2 11 14
3 12 13 14
3 18 17 13
4 14 15 16 17
0
0
0
2 18 20
1 19
1 20
6
1 20
8 20
15 16
11 4
7 13
2 16

my ACC program gets

Test Set #1
1 to 20: 7
2 to 9: 5
19 to 5: 6
18 to 19: 2
16 to 20: 2

Test Set #2
1 to 20: 4
8 to 20: 5
15 to 16: 2
11 to 4: 1
7 to 13: 3
2 to 16: 4

Test Set #3
1 to 20: 7
2 to 9: 5
19 to 5: 6
18 to 19: 2
16 to 20: 2

Test Set #4
1 to 20: 4
8 to 20: 5
15 to 16: 2
11 to 4: 1
7 to 13: 3
2 to 16: 4

Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

hotovaga
New poster
Posts: 4
Joined: Mon Nov 29, 2010 9:35 pm

### Re: 567 (Risk) - Wrong Answer

hey can anyone pls help me, where is the problem in this code? I used bfs to solve this problem.Thanks in advance.

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;

bool M[30][30];

int do_bfs(int city1,int city2)
{
queue<int> q;
int d[20]={0};
bool seen[20];

for(int i=0;i<20;i++)
seen[i]=false;

int s= city1 -1;  //source vertex;
int destination= city2 -1; //destination vertex
int v;

seen[s]=true;
d[s]=0;
if(s==destination)
return 0;
q.push(s);

while(!q.empty()){

int u= q.front();
q.pop();

for(v=0;v<20;v++){

if(M[u][v] && !seen[v]){
seen[v]=true;
d[v]=d[u]+1;
if(v==destination)
return d[v];
else
q.push(v);
}

}

seen[u]=true;
}
return d[destination];
}

int main()
{
int X,b,i,j,tc,city1,city2, ts=1;
while(1){

memset(M,0,sizeof(M));
if(!(cin>>X)) break;

for(i=0;i<X;i++){
cin>>b;
M[0][b-1]=1;
M[b-1][0]=1;
}

for(i=1;i<19;i++){
cin>>X;
char c=getchar();
if( X>0 && c=='\n'){
tc=X;
goto test_case;
}
for(j=0;j<X;j++){
cin>>b;
M[i][b-1]=1;
M[b-1][i]=1;
}
}

cin>>tc;
test_case:

cout<<"Test set #"<<ts++<<endl;
for(i=0;i<tc;i++){
cin>>city1>>city2;

int res=do_bfs(city1,city2);

printf("%2d to %2d:%2d\n",city1,city2,res);
}
cout<<endl;
}

return 0;
}

``````

BUET
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

### 567 (Risk) - WA

what's the problem in this code?

Code: Select all

``````#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<cstdio>

using namespace std;

#define  un 0
#define  dis 1
#define comp 2;

queue<int> q;

int step;

int state[25];

bool flag[25];

int in_queue[25];

int p[25];

int src,dest;

int BFS()
{

int u,i;

memset(flag,false,sizeof(flag));

memset(p,-1,sizeof(p));

//state[src] = dis;

p[src] = -1;

flag[src] = true;

q.push(src);

while(!q.empty())
{
u = q.front();
q.pop();

int  tmp;
int size;

for(i = 0; i < adj[u].size(); i++)
{

{

step = 0;
int se = dest;
while(p[se] != -1)
{
se = p[se];
step++;
}

while(!q.empty())
q.pop();

//cout << "Finish\n";

return 1;

}
else
{

{
}
}
}

state[u] = comp;

}

return 1;

}

int main(void)
{

int i,j,a,b;

int t = 1;;

i = 0;

while((scanf("%d",&a)) ==1)
{

//cin >> a;

//if
//return 0;

for(j = 0; j<19; j++)
{
if(j != 0)
cin >> a;
for(i = 0;i < a; i++)
{
cin >> b;

}
}

cin >> b;

cout << "Test Set #" << t++ << endl;

for( i = 0; i < b; i++)
{
cin >> src >> dest;

BFS();

printf("%2d to %2d: %d\n",src,dest,step);

}

cout << endl;

for(i = 0; i <= 19;i++)

}

return 0;
}
[color=#FF80FF][color=#FF80FF][quote]"No quote"[/quote]``````

Mohayemin
New poster
Posts: 2
Joined: Thu Apr 28, 2011 6:07 pm

### Re: 567 (Risk) - Wrong Answer

The array GRAPH stores the graph.
GRAPH[0] stores the degree of i-th node.

Code: Select all

``````#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>

#define SIZE 25

#define WHTE 0
#define GRAY 1
#define BLCK 2

using namespace std;

int GRAPH[SIZE][SIZE];

int BFS(int src, int dst);

int main (){
int N, u, v;
int A, B;
int d;
int t = 0;
int X, Y;
while(scanf("%d", &X)!=EOF){
for (u = 1; u <= 20; u++){
GRAPH[u][0] = 0;
}

u = 1;
for (d = 1; d <= X; d++){
scanf("%d", &Y);
GRAPH[u][0]++;
GRAPH[u][GRAPH[u][0]] = Y;
GRAPH[Y][0]++;
GRAPH[Y][GRAPH[Y][0]] = u;
}

for (u = 2; u <= 19; u++){
scanf("%d", &X);
GRAPH[u][0]+=X;

for (d = 1; d <= X; d++){
scanf("%d", &Y);
GRAPH[u][0]++;
GRAPH[u][GRAPH[u][0]] = Y;
GRAPH[Y][0]++;
GRAPH[Y][GRAPH[Y][0]] = u;
}
}

scanf("%d", &N);
printf("Test Set #%d\n", ++t);
while (N--){
scanf("%d %d", &A, &B);
printf("%2d to %2d: %d\n", A, B, BFS(A, B));
}

puts("");
}

return 0;
}

int BFS(int src, int dst){
int u, v;
int V;
int C[SIZE];
int D[SIZE];
int P[SIZE];

queue<int> Q;

if (src > dst){
src^=dst;
dst^=src;
src^=dst;
}

for (u = 1; u <= 20; u++){
C[u] = WHTE;
D[u] = -1;
P[u] = -1;
}

C[src] = GRAY;
D[src] = 0;
P[src] = -1;

Q.push(src);

while (!Q.empty()){
u = Q.front();
Q.pop();
for (v = 1; v <= GRAPH[u][0]; v++){
V = GRAPH[u][v];

if (C[V] == WHTE){
C[V] = GRAY;
D[V] = D[u]+1;
P[V] = u;
Q.push(V);
}
}
C[u] = BLCK;
}

return D[dst];
}``````

live_lie
New poster
Posts: 19
Joined: Mon Nov 29, 2010 11:50 pm

### Re: 567 (Risk) - Wrong Answer

you can use a simple bfs here....and check the output foramat....the newline metter.

mahbub.cse.kuet
New poster
Posts: 3
Joined: Thu Sep 03, 2009 8:53 pm

### 567 (Risk) - WA

Already got WA 7 times and I surprised why ? Need a kind person who provide me critical input ?
I used Floyd. Thanks in advance.

Code: Select all

``````int dist[22][22];

void Init()
{
FOR(i, 0, 21) {
FOR(j, 0, 21)
dist[i][j] = INF;
dist[i][i] = 0;
}

}
void FloydWarshall()
{
FOR(i, 0, 21)
FOR(j, 0, 21)
FOR(k, 0, 21)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

int main()
{
WRITE("output.txt");

int i, j, k;
int TC, tc;
int n, N, temp;
int node, s, t;

tc = 1;
while(cin >> n) {
Init();
FOR(node, 1, 19) {
if(node != 1) cin >> n;

FOR(j, 1, n) {
cin >> temp;
dist[node][temp] = dist[temp][node] = 1;
}
}

FloydWarshall();

cout << "Test Set #" << tc++ << "\n";
cin >> N;

FOR(i, 1, N) {
cin >> s >> t;
//          printf("%2d to %2d: %d\n", s, t, dist[s][t]);
printf("%2d to %2d: %d\n", s, t, dist[s][t]);
}
cout << "\n";
}

return 0;
}
``````

Blackwizard
New poster
Posts: 12
Joined: Fri May 25, 2012 5:36 pm

### WA in 567

Hi...I've used bfs algorithm to solve this problem...it past sample input and some another testcases I've test...but I don't know why it goes wrong!!!
Here's my code...

Code: Select all

``````#include <iostream>
#include <queue>
#include <cstring>
#include <stdio.h>

using namespace std;

int mat[21][21];
int mark[21];
int tc = 0;
int n, m, t;
int a, b;

void bfs ()
{
queue <int> q;
q.push (a);
mark[a] = 0;
while (!q.empty())
{
int temp = q.front();
q.pop();
if (temp == b)
return;
for (int i = 1; i <= 20; i++)
if (mat[temp][i] == 1 && mark[i] == -1)
{
q.push (i);
mark[i] = mark[temp] + 1;
}
}
}

int main ()
{
//freopen ("input.in", "r", stdin);
while (!cin.eof())
{
tc++;
for (int i = 0; i < 21; i++)
memset (mat[i], 0, sizeof mat[i]);
for (int i = 1; i <= 19 && cin >> n; i++)
for (int j = 0; j < n && cin >> m; j++)
{
mat[i][m] = 1;
mat[m][i] = 1;
}
cin >> t;
cout << "Test Set #" << tc << endl;
for (int i = 0; i < t && cin >> a >> b; i++)
{
memset (mark, -1, sizeof mark);
bfs ();
printf ("%2d", a);
cout << " to ";
printf ("%2d", b);
cout << ": " << mark[b] << endl;
}
cout << endl;
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: WA in 567

Don't loop until !cin.eof(), that won't work if there is a space at the end of the input file.
Check input and AC output for thousands of problems on uDebug!