Page 6 of 9

Re: 336 WA

Posted: 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
``````

Re: 336 WA

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

Re: 336 WA

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

Code: Select all

``````AC
``````

Re: 336 WA

Posted: 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.

Re: 336 WA

Posted: Sat May 12, 2012 7:57 pm
WA !!!!!!

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
Edit: removed wrong I/O.

Getting TLE!!!

Posted: Wed Jul 11, 2012 7:57 am
cut

Re: 336 WA

Posted: 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]

Re: 336 WA

Posted: 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.

Re: 336 WA

Posted: 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.

Re: 336 WA

Posted: 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);
}
}
}
``````

Re: 336 WA

Posted: 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.

Re: 336 WA

Posted: Fri Nov 09, 2012 8:25 pm

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>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]);
}
}
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++)
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();
{
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
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
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);

}

}

}