336 - A Node Too Far

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

Moderator: Board moderators

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 336 WA

Post by Scarecrow » Sun Apr 29, 2012 3:38 pm

why am I getting RE in this problem? can't figure it out. can any1 help plz?

Code: Select all

AC
Last edited by Scarecrow on Mon Jul 16, 2012 8:31 pm, edited 1 time in total.
Do or do not. There is no try.

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

Re: 336 WA

Post by brianfry713 » Wed May 02, 2012 2:59 am

TTL can be greater than 50.
Check input and AC output for thousands of problems on uDebug!

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 336 WA

Post by Scarecrow » Wed May 02, 2012 2:26 pm

fixing the RE, now i get WA :(

Code: Select all

AC
Last edited by Scarecrow on Mon Jul 16, 2012 8:32 pm, edited 1 time in total.
Do or do not. There is no try.

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

Re: 336 WA

Post by brianfry713 » Thu May 03, 2012 12:34 am

There is a case where a node is connected to itself. This causes your graph to be constructed incorrectly.
Check input and AC output for thousands of problems on uDebug!

shatil_cse
New poster
Posts: 11
Joined: Thu Apr 05, 2012 8:33 pm

Re: 336 WA

Post by shatil_cse » Sat May 12, 2012 7:57 pm

WA !!!!!!
please help me..........

Code: Select all

#include<stdio.h>
int a,t,front,rear,level,nc,q[100000],i,j,k,l,m,n,x[10000][10000],y[10000],z[100000],state[10000];
int main()
{
	scanf("%d",&nc);
	for(l=1;nc!=0;l+=j-1)
	{
		for(i=0;i<10000;i++) x[i][0]=1;
		t=0;
		for(i=1;i<=nc;i++)
		{
			scanf("%d%d",&m,&n);                     //I have store all node I can go directly from a node(index) in two dimentional array
													 //x[m][0] indicates how many node I can go from node m.
			if(x[m][0]==1) t++;
			x[m][x[m][0]++]=n;
			if(x[n][0]==1) t++;
			x[n][x[n][0]++]=m;
		}
		scanf("%d%d",&y[1],&z[1]);
		for(k=1;y[k]!=0||z[k]!=0;) scanf("%d%d",&y[k],&z[++k]);       
		for(j=1;j<k;j++)
		{
			for(i=0;i<10000;i++) state[i]=0;             //initializing the state 
			rear=1;
			front=1;
			level=1;
			a=0;
			q[rear]=y[j];
			n=y[j];
			for(i=1;rear>=front&&a!=z[j];i++)           //traversing the node.
			{
				state[n]++;
				for(m=1;m<x[n][0];m++)
				{
					if(state[x[n][m]]==0)
					{
						q[++rear]=x[n][m],state[x[n][m]]++;
					}
				}
				if(front==level) level=rear,a++;
				n=q[++front];
			}
			printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",l+j-1,t-rear,y[j],z[j]);
		}
		scanf("%d",&nc);
	}
	return 0;
}

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

Re: 336 WA

Post by brianfry713 » Mon May 14, 2012 11:14 pm

Edit: removed wrong I/O.
Last edited by brianfry713 on Wed Oct 24, 2012 7:21 pm, edited 2 times in total.
Check input and AC output for thousands of problems on uDebug!

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Getting TLE!!!

Post by mahade hasan » Wed Jul 11, 2012 7:57 am

cut
Last edited by mahade hasan on Sun Nov 04, 2012 1:49 am, edited 1 time in total.
we r surrounded by happiness
need eyes to feel it!

binitam
New poster
Posts: 1
Joined: Fri Jul 13, 2012 8:20 pm

Re: 336 WA

Post by binitam » Fri Jul 13, 2012 8:46 pm

Code: Select all

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main()
{
	int nc,nEdge,a,b,i,root,ttl,cases=1;
	while(1)
	{
		
		
			vector<int>edges[10000];
			cin>>nc;
			
			if(nc==0)break;
		
			for(i=0;i<nc;i++)
			{
				cin>>a>>b;
				if(a==0&&b==0)break;
				edges[a].push_back(b);
				edges[b].push_back(a);
				

			}
			while(1)
			{
				int v,visited[10000]={0},dist[10000]={0},u,count=0,flag=0;
				
				cin>>root>>ttl;
				if(root==0&&ttl==0)
				{
					flag=1;

					break;
				}
				queue<int>q;
				q.push(root);
				while(!q.empty())
				{
					v=q.front();
					visited[v]=1;
					for(i=0;i<edges[v].size();i++)
					{
						u=edges[v][i];

						if(!visited[u])
						{
							visited[u]=1;
							dist[u]=dist[v]+1;
							
							if(dist[u]>ttl)count++;

							q.push(u);
						}


					}
					q.pop();
					
				}
				if(!flag)
				cout<<"Case "<<cases<<": "<<count<<" nodes not reachable from node "<<root<<" with TTL = "<<ttl<<"."<<'\n';
				cases++;

			}

	}
	return 0;
}
IT IS GIVING WA,,,cant understand,,plz help


[quote][/quote]

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

Re: 336 WA

Post by brianfry713 » Tue Jul 17, 2012 12:37 am

mahade hasan, running memset on your large MainArry every test case is slow. no network will contain more than 30 nodes. My AC code assumes each node can be any 32-bit signed integer.
Check input and AC output for thousands of problems on uDebug!

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

Re: 336 WA

Post by brianfry713 » Tue Jul 17, 2012 12:38 am

binitam, no network will contain more than 30 nodes. My AC code assumes each node can be any 32-bit signed integer.
Check input and AC output for thousands of problems on uDebug!

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 336 WA

Post by @ce » Wed Oct 24, 2012 6:23 am

Getting WA...plz help

Code: Select all

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<deque>
#include<queue>
#include<map>
#include<utility>

#define L long long int
#define U unsigned long long int
using namespace std;

int arr[111][111];
map <int,int>m;
vector < pair<int,int> >v;

main()
{
      int t = 1;
      while(1)
      {
            int n,p=0;
            cin>>n;
            m.clear();
            v.clear();
            if(!n)
                  break;
            for(int i = 0;i<n;i++)
            {
                  int a,b;
                  cin>>a>>b;
                  if(!(a|b))
                        break;
                  //cout<<a<<b<<endl;
                  if(m.find(a) == m.end())
                        m.insert(make_pair(a,p++));
                  if(m.find(b) == m.end())
                        m.insert(make_pair(b,p++));
                  v.push_back(make_pair(a,b));

            }

            for(int i = 0;i<m.size();i++)
            {
                  for(int j = 0;j<m.size();j++)
                        arr[i][j] = -1;
            }
            for(int i = 0;i<n;i++)
            {
                  int a = m.find(v[i].first)->second ;
                  int b = m.find(v[i].second)->second;
                  arr[a][b] = 1;
                  arr[b][a] = 1;
            }

            for(int k = 0;k<m.size();k++)
            {
                  for(int i= 0;i<m.size();i++)
                  {
                        for(int j = 0;j<n;j++)
                        {
                              if(i == j)
                                    arr[i][j] = 0;
                              else if(arr[i][j] == -1)
                              {
                                    if(arr[i][k] != -1 && arr[k][j] != -1)
                                          arr[i][j] = arr[i][k] + arr[k][j];
                              }
                              else
                              {
                                    if(arr[i][k] != -1 && arr[k][j] != -1)
                                          arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
                              }
                        }
                  }
            }

            int src,ttl;
            while(1)
            {
                  cin>>src>>ttl;
                  if(!(src|ttl))
                        break;
                  int c = 0;
                  for(int i = 0;i<m.size();i++)
                  {
                        if(src == i)
                              continue;
                        int x = m.find(src)->second;
                        if(arr[x][i] > ttl || arr[x][i] == -1)
                              c++;
                  }
                  printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",t++,c,src,ttl);
            }
      }
}
-@ce

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

Re: 336 WA

Post by brianfry713 » Sat Oct 27, 2012 2:16 am

@ce, I was able to make your code AC with two small changes.
In Floyd-Warshall, all the limits should be m.size().
On line 93 you have

Code: Select all

                        if(src == i)
                              continue;
Delete that and check if(x==i) instead.
Check input and AC output for thousands of problems on uDebug!

alimbubt
New poster
Posts: 39
Joined: Tue Aug 07, 2012 10:40 pm
Location: BUBT,Dhaka, Bangladesh
Contact:

Re: 336 WA

Post by alimbubt » Fri Nov 09, 2012 8:25 pm

I am getting continuously WA.....Please help me or give me some critical test case in which my code shows wrong answer.. :(

Code: Select all

#include<cstdio>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<bitset>
#include<string>
#include <sstream>
#include <fstream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define pi 2*acos(0.0)
using namespace std;

int BFS(int start,int ttl);
vector<int>adj[40];
vector<int>vec;
map<int,int>mp;

int main()
{
    int nc,node,i,f,u,v,j,start,ttl,t=0;
    while(scanf("%d",&nc)==1)
    {
        if(nc==0) break;
        f=0;
        for(i=1;i<=nc;i++)
        {
            scanf("%d%d",&u,&v);
            if(mp[u]==0)
            {
                mp[u]=++f;
                vec.push_back(mp[u]);
            }
            if(mp[v]==0)
            {
                mp[v]=++f;
                vec.push_back(mp[v]);
            }
            adj[mp[u]].push_back(mp[v]);
            adj[mp[v]].push_back(mp[u]);
        }
        sort(vec.begin(),vec.end());
        node=vec.size();
        while(scanf("%d%d",&start,&ttl)==2)
        {
            int count;
            if(start==0&&ttl==0) break;
            int start1=start;
            if(mp[start]==0)
            {
                printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++t,vec.size(),start1,ttl);
                continue;
            }
            start=mp[start];
            count=BFS(start,ttl);
            printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++t,vec.size()-count,start1,ttl);
        }
        for(i=1;i<=node;i++)
        adj[i].clear();
        vec.clear();
        mp.clear();
    }
    return 0;
}


int BFS(int start,int ttl)
{
    int dist[50]={0};
    int count=1,i;
    map<int,int>mpp;
    mpp[start]=1;
    queue<int>q;
    q.push(start);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(i=0;i<adj[u].size();i++)
        {
            int v=adj[u][i];
            dist[v]=dist[u]+1;
            mpp[v]++;
            if(mpp[v]>1) continue;
            if(dist[v]<=ttl)
            count++;
            if(dist[v]<=ttl-1)
            q.push(v);
        }
    }
    mpp.clear();
    return count;
}
Give me six hours to chop down a tree and I will spend the first four sharpening the axe...(BUBT ILLUSION)
http://uhunt.felix-halim.net/id/155497
http://onlyprogramming.wordpress.com/

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

Re: 336 WA

Post by brianfry713 » Fri Nov 09, 2012 9:06 pm

Input

Code: Select all

2
1 1  1 2
1 1  0 0

0
Correct output:

Code: Select all

Case 1: 0 nodes not reachable from node 1 with TTL = 1.
Check input and AC output for thousands of problems on uDebug!

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

Re: 336 WA

Post by sumit saha shawon » Sat Nov 17, 2012 4:20 pm

why I am getting WA??
My code:

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<string.h>
using namespace std;
int main()
{
int edges;
int x,y;
int src,ttl,kase=1;
vector<int>G[100000];
set<int>s;

while(cin>>edges&&edges)
{
// cout<<edges<<endl;
// memset(G,0,sizeof G);
for(int i=0;i<100000;i++)
G.clear();
s.clear();

for(int i=1; i<=edges; i++)
{
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
s.insert(x);
s.insert(y);

}
// cout<<s.size()<<endl;
while(cin>>src>>ttl)
{
int count=1;
if(src==0&&ttl==0)
break;
// printf("Case %d: %d %d\n",kase++,src,ttl);
queue<int>q;
q.push(src);
int visited[100000]= {0},dis[100000];
visited[src]=1,dis[src]=0;
while(!q.empty())
{
int u=q.front();
for(int i=0; i<G.size(); i++)
{
int v=G;
if(!visited[v])
{

dis[v]=dis+1;
if(dis[v]>ttl)
break;
q.push(v);
visited[v]=1;

count++;


}

}
q.pop();
}
// cout<<s.size()-count<<endl;
int ans=s.size()-count;
if(ans<0)
ans=0;
printf("Case %d: %d nodes not reachable from node %d with TTL = %d\n.",kase++,ans,src,ttl);


}



}

}

Post Reply

Return to “Volume 3 (300-399)”