567 - Risk

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: WA in 567

Post by Blackwizard » Fri Jun 01, 2012 3:13 pm

yes...you're true!!!
thanks a lot...

sumit saha shawon
New poster
Posts: 19
Joined: Tue Jun 26, 2012 9:19 pm

Re: WA in 567

Post by sumit saha shawon » Fri Nov 30, 2012 12:16 am

why getting wa?? :o
code:

Code: Select all

#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
vector<int>v[100];
int ans;
void bfs(int src,int des)
{
    queue<int>q;
    q.push(src);
    int taken[100]= {0},distance[100];
    taken[src]=1;
    distance[src]=0;
    while(!q.empty())
    {
        int u=q.front();
        for(int i=0; i<v[u].size(); i++)
        {
            int t=v[u][i];
            if(!taken[t])
            {
                distance[t]=distance[u]+1;
                taken[t]=1;
                q.push(t);
                if(t==des)
                {
                    ans=distance[t];
                    return;
                }
            }
 
        }
         q.pop();
    }
}
int main()
{
    int n,a,x,y,t,src,des,kase=1;
    while(cin>>n)
    {
        for(int i=1; i<=n; i++)
        {
            cin>>y;
            v[1].push_back(y);
            v[y].push_back(1);
        }
        for(x=2; x<20; x++)
        {
            cin>>n;
            for(int i=1; i<=n; i++)
            {
                cin>>y;
                v[x].push_back(y);
                v[y].push_back(x);
            }
 
        }
 
 
        //if(kase!=1)
        //puts("");
        printf("Test Set #%d\n",kase++);
        cin>>t;
        for(int i=1; i<=t; i++)
        {
            cin>>src>>des;
            printf("%2d to %2d: ",src,des);
            if(src==des)
            cout<<"0\n";
            else
            {
                bfs(src,des);
                cout<<ans<<endl;
            }
 
 
 
        }
       puts("");
        for(int i=0; i<20; i++)
            v[i].clear();
    }
 
}
Last edited by brianfry713 on Mon Dec 01, 2014 10:12 pm, edited 1 time in total.
Reason: Added code blocks

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

Re: WA in 567

Post by brianfry713 » Fri Nov 30, 2012 9:27 pm

change line 81 to:
for(int i=0; i<=20; i++)
Check input and AC output for thousands of problems on uDebug!

Sabiha_Fancy
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

Re: 567 (Risk) - Wrong Answer

Post by Sabiha_Fancy » Wed Jan 23, 2013 4:34 pm

I am getting run time error. but i am unable to find out the error. if anyone help i will be glad.
here is my code

Code: Select all


#include<stdio.h>
#include<string.h>

void BFS(int i);
int dequeue();
void enqueue(int k);

struct node {
	int node_value;
	char color[7];
} V[21];

int a[21][21];
int s[110][2];
int main()
{
	int i,j,n,m,N,T;
	T=1;
	for(i=1; i<=20; ++i)
	{
		for(j=1; j<=20; ++j)
			a[i][j] = 0;
	}
	while(scanf("%d",&n)==1)
	{
		for(j=1; j<=n; ++j)
		{
			scanf("%d",&m);
			a[1][m] = 1;
			a[m][1] = 1;
		}
		for(i=2; i<=19; ++i)
		{
			scanf("%d",&n);
			for(j=1; j<=n; ++j)
			{
				scanf("%d",&m);
				a[i][m] = 1;
				a[m][i] = 1;
			}	
		}
		scanf("%d",&N);
		for(i=1; i<=N; ++i)
		{
			scanf("%d %d",&s[i][0],&s[i][1]);
		}
		printf("Test Set #%d\n",T);
		T++;
		for(i=1; i<=N; ++i)
		{
			for(j=1; j<=20; ++j)
			{
				strcpy(V[j].color,"WHITE");
			}
			BFS(i);
			printf("%2d to %2d: %d\n",s[i][0],s[i][1],V[s[i][1]].node_value);
		}
		printf("\n");
		for(i=1; i<=20; ++i)
		{
			for(j=1; j<=20; ++j)
				a[i][j] = 0;
		}
	}
	return 0;
}
int Q[21];
int tail,front;
void BFS(int i)
{
	int u,k;
	strcpy(V[s[i][0]].color,"GRAY");
	V[s[i][0]].node_value = 0;
	tail = front = 0;
	Q[front] = s[i][0];
	tail++;
	while(front<=tail)
	{
		u = dequeue();
		for(k=1; k<=20; ++k)
		{
			if(a[u][k] == 1)
			{
				if(strcmp(V[k].color,"WHITE")==0)
				{
					strcpy(V[k].color,"GRAY");
					V[k].node_value = V[u].node_value+1;
					enqueue(k);
				}
			}
		}
	}
}

int dequeue()
{
	int x;
	if(front<=tail)
	{
		x = Q[front];
		front++;
		return x;
	}
	else
		return -1;
}
void enqueue(int k)
{
	if(tail<20)
	{
		Q[tail] = k;
		tail++;
	}
}
Last edited by brianfry713 on Mon Dec 01, 2014 10:13 pm, edited 1 time in total.
Reason: Added code blocks
Fancy

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

Re: 567 (Risk) - Wrong Answer

Post by brianfry713 » Thu Jan 24, 2013 8:16 pm

The problem statement lied, N may be bigger than 100. Just print out the result after reading each country pair so you don't have to store them all.
Check input and AC output for thousands of problems on uDebug!

Sabiha_Fancy
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

Re: 567 (Risk) - Wrong Answer

Post by Sabiha_Fancy » Fri Jan 25, 2013 5:17 pm

Thank you for your reply. I got accepted.
Fancy

laituanksa245
New poster
Posts: 20
Joined: Tue Jan 10, 2012 4:23 pm
Location: Vietnam

SubmissionErr 567 Risk

Post by laituanksa245 » Mon Feb 11, 2013 5:26 pm

I keep getting "SubmissionErr". What does that mean ? What should I do ?

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

Re: SubmissionErr 567 Risk

Post by brianfry713 » Mon Feb 11, 2013 10:26 pm

That seems to show up in some problems. It could be an issue with your code, maybe a TLE.
Check input and AC output for thousands of problems on uDebug!

AnindyaPaul
New poster
Posts: 5
Joined: Sat Apr 06, 2013 12:42 pm
Location: Dhaka, Bangladesh
Contact:

Re: 567 (Risk) - Wrong Answer

Post by AnindyaPaul » Sat Jul 20, 2013 11:08 am

What is wrong here? Why WA? I have used simple BFS by queue.

Code: Select all

//  Program : UVa 567 - Risk
//  Author  : Anindya Sundar Paul
//  Run-time:
//  Verdict : WA

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>

#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>

#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <bitset>

#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>

using namespace std;

#define EPS 1e-9
#define INF 2147483647
#define PI 3.14159265358979323846264338327950

#define MEM( x, y ) memset( x, y, sizeof( x ) )
#define READ( file ) freopen( file, "r", stdin )
#define WRITE( file ) freopen( file, "w", stdout )

#define PB( x ) push_back( x )
#define PF( x ) push_front( x )

typedef long long LL;
typedef unsigned long long ULL;

// Sieve Prime Generator
template <class T> T setBit( T n, T pos ) { return n = n | ( 1 << pos ); }
template <class T> bool checkBit( T n, T pos ) { return n & ( 1 << pos ); }

// Template ends, coding starts

int lev[21];
int visit[21];
int dis[21][21];

vector <int> node[21];

int findDis( int src, int lev );

int main()
{
    //READ( "i.txt" );

    int n, pos, from, to, line = 1, cs = 1;

    while( cin >> n ) {
        if( line < 20 ) {
            while( n-- ) {
                cin >> pos;
                node[line].PB( pos );
                node[pos].PB( line );
            }
            line++;
        }
        else {
            line = 1;
            if( cs != 1 ) puts( "" );
            cout << "Test Set #" << cs++ << endl;

            while( n-- ) {
                MEM( lev, 0 );
                MEM( visit, 0 );
                cin >> from >> to;
                printf( "%2d to %2d:%2d\n", from, to, findDis( from, to ) );
            }
            for( LL i = 0; i < 21; i++ )
                node[i].clear();
        }
    }

    return 0;
}

int findDis( int src, int target )
{
    LL f, x, i;
    queue <int> q;

    q.push( src );
    lev[src] = 0;
    visit[src] = 1;

    while( !q.empty() ) {
        f = q.front();
        if( f == target ) break;
        for( i = 0; i < node[f].size(); i++ ) {
            x = node[f][i];
            if( !visit[x] ) {
                lev[x] = lev[f] + 1;
                visit[x] = 1;
                q.push( x );
            }
        }
        q.pop();
    }

    return lev[f];
}

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

Re: 567 (Risk) - Wrong Answer

Post by brianfry713 » Tue Jul 23, 2013 12:52 am

Following all result lines of each input set, your program should print a single blank line.
Print a blank line after the last input set.
Check input and AC output for thousands of problems on uDebug!

AnindyaPaul
New poster
Posts: 5
Joined: Sat Apr 06, 2013 12:42 pm
Location: Dhaka, Bangladesh
Contact:

Re: 567 (Risk) - Wrong Answer

Post by AnindyaPaul » Tue Jul 23, 2013 2:44 pm

Thanks! AC. :D

reza_ju_cse
New poster
Posts: 1
Joined: Tue May 13, 2014 11:31 pm

567- Risk (getting WA)

Post by reza_ju_cse » Tue May 13, 2014 11:49 pm

hello , i m a newbie :roll:
... seeking uor help badly .... why i'm getting WA ... i've all the case right ... :(

my code >>> http://pastebin.com/AK0W8S3U

... let my code be focused by u ... thanks in advance ... :D

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

Re: 567- Risk (getting WA)

Post by brianfry713 » Wed May 14, 2014 7:37 pm

Check input and AC output for thousands of problems on uDebug!

Karkat_Vantas
New poster
Posts: 4
Joined: Thu Aug 21, 2014 2:59 am

Re: 567 - Risk

Post by Karkat_Vantas » Thu Nov 27, 2014 10:42 pm

I don't understand why my code gives a compiler error. Eclipse lets me run it, but uHunt doesn't. Does anyone know why this happens? Thank you for your help.

Code: Select all

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Bag<Integer>[] connect;
		boolean[] marked;
		int[] dist;
		int x;
		int q;
		int start;
		int end;
		int trial=1;
		Scanner in = new Scanner(System.in);
		while(in.hasNext())
		{
			connect =(Bag<Integer>[]) new Bag[21];  // if I had to guess, the problem is here, but i don't know why or how to fix it
			for(int i=0;i<21;i++)
			{
				connect[i]=new Bag<Integer>();
			}
			for(int i=1;i<20;i++)
			{	
				x=in.nextInt();
				for(int j=0;j<x;j++)
				{
					q=in.nextInt();

					connect[i].add(q);
					connect[q].add(i);
				}
			}
			x=in.nextInt();
			System.out.println("");
			System.out.println("Test Set #"+trial);
			trial++;
			
			for(int i=0;i<x;i++)
			{
				start=in.nextInt();
				end=in.nextInt();
				Queue<Integer> w = new Queue<Integer>();
				dist=new int[21];
				int[] edgeTo=new int[21];
				marked= new boolean[21];
				marked[start]=true;
				w.enqueue(start);
				while(!w.isEmpty())
				{
					q=w.dequeue();
					if(q==end)
						break;
					for(int z : connect[q])
					{
						if(!marked[z])
						{
							marked[z]=true;
						dist[z]=dist[q]+1;
						edgeTo[z]=q;
						w.enqueue(z);
						}
						}
				
				}
				System.out.printf("%2d to %2d: %-2d\n",start,end,dist[end]);
			}
			
		}
		System.out.println("");


	}


}

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 567 - Risk

Post by lighted » Fri Nov 28, 2014 12:54 pm

http://uva.onlinejudge.org/index.php?op ... n=14596911
Click on My Submissions to see reason of CE. It is because of Bag.

Java doesn’t have a Bag interface or an implementation. There is no Bag collection in Java. (It is not a standart collection. It is Hibernate-specific). Try List instead of Bag. http://stackoverflow.com/questions/1560 ... -framework
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 5 (500-599)”