Page 6 of 9

Re: 336 WA

Posted: Sun Apr 29, 2012 3:38 pm
by Scarecrow
why am I getting RE in this problem? can't figure it out. can any1 help plz?

Code: Select all

AC

Re: 336 WA

Posted: Wed May 02, 2012 2:59 am
by brianfry713
TTL can be greater than 50.

Re: 336 WA

Posted: Wed May 02, 2012 2:26 pm
by Scarecrow
fixing the RE, now i get WA :(

Code: Select all

AC

Re: 336 WA

Posted: Thu May 03, 2012 12:34 am
by brianfry713
There is a case where a node is connected to itself. This causes your graph to be constructed incorrectly.

Re: 336 WA

Posted: Sat May 12, 2012 7:57 pm
by shatil_cse
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;
}

Re: 336 WA

Posted: Mon May 14, 2012 11:14 pm
by brianfry713
Edit: removed wrong I/O.

Getting TLE!!!

Posted: Wed Jul 11, 2012 7:57 am
by mahade hasan
cut

Re: 336 WA

Posted: Fri Jul 13, 2012 8:46 pm
by binitam

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]

Re: 336 WA

Posted: Tue Jul 17, 2012 12:37 am
by brianfry713
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.

Re: 336 WA

Posted: Tue Jul 17, 2012 12:38 am
by brianfry713
binitam, no network will contain more than 30 nodes. My AC code assumes each node can be any 32-bit signed integer.

Re: 336 WA

Posted: Wed Oct 24, 2012 6:23 am
by @ce
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);
            }
      }
}

Re: 336 WA

Posted: Sat Oct 27, 2012 2:16 am
by brianfry713
@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.

Re: 336 WA

Posted: Fri Nov 09, 2012 8:25 pm
by alimbubt
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;
}

Re: 336 WA

Posted: Fri Nov 09, 2012 9:06 pm
by brianfry713
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.

Re: 336 WA

Posted: Sat Nov 17, 2012 4:20 pm
by sumit saha shawon
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);


}



}

}