567 - Risk
Moderator: Board moderators
-
- New poster
- Posts: 20
- Joined: Thu Jan 17, 2008 10:47 pm
- Location: India
Re: 567 (Risk) - Wrong Answer
Please help.. I am getting WA 

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"
Re: 567 (Risk) - Wrong Answer
I got wrong answer, too
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;
}
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;
}
Re: 567 (Risk) - Wrong Answer
AC.........
Re: 567 (Risk) - Wrong Answer
Excuse me dodouuu...could tell me how did you make your code accepted? Thanks in advance.
-
- New poster
- Posts: 3
- Joined: Sun Jun 13, 2010 9:37 pm
- Location: CSEDU,Dhaka,Bangladesh
- 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.
I used simple bfs.
Code: Select all
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
- Location: narayangong,bangladesh.
- 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
But your program output wrong.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com
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;
}
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;
vector<int>adj[25];
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;
size = adj[u].size();
for(i = 0; i < adj[u].size(); i++)
{
tmp = adj[u][i];
if(adj[u][i] == dest)
{
step = 0;
p[adj[u][i]] = u;
int se = dest;
while(p[se] != -1)
{
se = p[se];
step++;
}
while(!q.empty())
q.pop();
//cout << "Finish\n";
return 1;
}
else
{
if(flag[ adj[u][i] ] == false)
{
flag[ adj[u][i] ] = true;
p[adj[u][i]] = u;
q.push(adj[u][i]);
}
}
}
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;
adj[j+1].push_back(b);
adj[b].push_back(j+1);
}
}
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++)
if(!adj[i].empty())
adj[i].clear();
}
return 0;
}
[color=#FF80FF][color=#FF80FF][quote]"No quote"[/quote]
Re: 567 (Risk) - Wrong Answer
Getting wrong answer:
The array GRAPH stores the graph.
GRAPH[0] stores the degree of i-th node.
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];
}
Re: 567 (Risk) - Wrong Answer
you can use a simple bfs here....and check the output foramat....the newline metter.
-
- 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.
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()
{
READ("input.txt");
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;
}
-
- 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...
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;
}
-
- 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!