336 - A Node Too Far

[Mohammad Mahmudur Rahman]

Did you consider these 2 cases?
1. The graph may be disconnected.
2. You can reach your starting node even if TTL = 0.

Test with this input

Code: Select all

5
1 2 2 3 3 4 4 5 6 7
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7

It should give

Code: Select all

Case 1: 6 nodes not reachable from node 1 with TTL = 0.
Case 2: 5 nodes not reachable from node 1 with TTL = 1.
Case 3: 4 nodes not reachable from node 1 with TTL = 2.
Case 4: 3 nodes not reachable from node 1 with TTL = 3.
Case 5: 2 nodes not reachable from node 1 with TTL = 4.
Case 6: 2 nodes not reachable from node 1 with TTL = 5.
Case 7: 2 nodes not reachable from node 1 with TTL = 6.
Case 8: 2 nodes not reachable from node 1 with TTL = 7.

[shihabrc]

Yes, it handles disconnected network. And it also produced correct output 4 ur input. And i've also checked the code 4 any wrong loops(like the one in 388 ).

the standing node is always considered reachable.
this code ensures it:

Code: Select all

if(d[i]>q) n++;

4 the standing node d=0. if(q==0) (q=TTL), then n(which counts the unreachable nodes) is not increased.

-Shihaib

[shihabrc]

Finally I've got AC. I just rewrote the code & this time used STL (set<>) to separate the nodes. All other things r same. My be my process of separating the nodes in the older code was wrong.

Thanks mahmud vai 4 ur I/Os.

-Shihab

[sunny]

i got plenty of WA's on prob336(A Node Too far).
pls give just one test case which my prog gives WA.



#include<stdio.h>
#include<stdlib.h>

struct node{
long name;
int noutdegree;
int outdegree[35];
}nodes[35];

struct node temp;
long s,TTL,nodename,queue[10000];
int visited[35],flag[35],total,prev,prevtotal;


void bfs(int u)
{
int i,j;
long ttl;
ttl=1;
while(ttl<=TTL)
{
for(i=prev;i<prevtotal;i++){
for(j=0;j<nodes[queue].noutdegree;j++){
if(visited[nodes[queue].outdegree[j]]) continue;
visited[nodes[queue].outdegree[j]]=1;
queue[total++]=nodes[queue].outdegree[j];
}
}
prev=prevtotal;
prevtotal=total;
ttl++;
}
}

int main()
{
int nc,i,j,k,v1,v2,x,n,q=0,nr;
long node1,node2;
while(scanf("%d",&nc)==1)
{
if(!nc) break;
x=0;
for(i=0;i<nc;i++){
scanf("%ld %ld",&node1,&node2);

for(j=0;j<x;j++) if(node1==nodes[j].name) break;
if(j==x) {x++;
nodes[j].name=node1;
nodes[j].noutdegree=0;}

v1=j;

for(j=0;j<x;j++) if(node2==nodes[j].name) break;
if(j==x) {x++;
nodes[j].name=node2;
nodes[j].noutdegree=0;}
v2=j;


nodes[v1].outdegree[nodes[v1].noutdegree]=v2;
nodes[v2].outdegree[nodes[v2].noutdegree]=v1;
nodes[v1].noutdegree++;
nodes[v2].noutdegree++;
}



scanf("%ld %ld",&s,&TTL);
while(s || TTL){
k=-1;
for(i=0;i<x;i++) {
if(nodes.name==s) k=i;
visited=0;
// flag=0;
}


total=0;
queue[total++]=k;
prevtotal=total;
prev=0;
visited[k]=1;
bfs(k);
nr=0;
for(j=0;j<x;j++) if(!visited[j]) nr++;
// dfs(k,0);

printf("Case %d: %d nodes not reachable from node %ld with TTL = %ld.\n",
++q,nr,s,TTL);

scanf("%ld %ld",&s,&TTL);
}
}
return 0;
}

[mamun]

After going through your code and failing to find anything wrong, I just submitted it and got RTE not WA . So it's some other case. Try to increase the arrays size.

[sunny]

actually following is my modified code which gets WA.
are the nodenames too big so long can't handle it?

what's the correct output 4 this:
1
1 1
1 0
0 0



#include<stdio.h>
#include<stdlib.h>

struct node{
long name;
int noutdegree;
int outdegree[35];
}nodes[35];

struct node temp;
long s,TTL,nodename,queue[10000];
int visited[35],flag[35],total,prev,prevtotal;


void bfs(int u)
{
int i,j;
long ttl;
ttl=1;
while(ttl<=TTL)
{
for(i=prev;i<prevtotal;i++){
for(j=0;j<nodes[queue].noutdegree;j++){
if(visited[nodes[queue].outdegree[j]]) continue;
visited[nodes[queue].outdegree[j]]=1;
queue[total++]=nodes[queue].outdegree[j];
}
}
prev=prevtotal;
prevtotal=total;
ttl++;
}
}

int main()
{
int nc,i,j,k,v1,v2,x,n,q=0,nr;
long node1,node2;
while(scanf("%d",&nc)==1)
{
if(!nc) break;
x=0;
for(i=0;i<nc;i++){
scanf("%ld %ld",&node1,&node2);

for(j=0;j<x;j++) if(node1==nodes[j].name) break;
if(j==x) {x++;
nodes[j].name=node1;
nodes[j].noutdegree=0;}

v1=j;

for(j=0;j<x;j++) if(node2==nodes[j].name) break;
if(j==x) {x++;
nodes[j].name=node2;
nodes[j].noutdegree=0;}
v2=j;


nodes[v1].outdegree[nodes[v1].noutdegree]=v2;
nodes[v2].outdegree[nodes[v2].noutdegree]=v1;
nodes[v1].noutdegree++;
nodes[v2].noutdegree++;
}



scanf("%ld %ld",&s,&TTL);
while(s || TTL){
k=-1;
for(i=0;i<x;i++) {
if(nodes.name==s) k=i;
visited=0;

}
if(k<0){
nr=x;
goto re;
}

total=0;
queue[total++]=k;
prevtotal=total;
prev=0;
visited[k]=1;
bfs(k);
nr=0;
for(j=0;j<x;j++) if(!visited[j]) nr++;

re:
printf("Case %d: %d nodes not reachable from node %ld with TTL = %ld.\n",
++q,nr,s,TTL);

scanf("%ld %ld",&s,&TTL);
}
}
return 0;
}

[Mohammad Mahmudur Rahman]

Code: Select all

Case 1: 0 nodes not reachable from node 1 with TTL = 0.

[ahsanlatif]

Hi,
I am getting RE from OJ. I have checked it on inputs provided on this site by others. It works fine, I can not understand what could have caused it. Can anybody help me? Here is my code:

Code: Select all

#include <iostream>
#include <queue>

using namespace std;

struct NODE{
	int NWID;
	int directConns;
	int connectedTo[30];
	char visited;
};
	
int getLoc(int NWID,NODE nw[],int curr_node){
	int i;
	for(i=0;i<curr_node;i++)
		if(nw[i].NWID==NWID)return i;
	return -1;
}


int countReachAbles(int nodeID,int TTL,NODE network[],int curr_node){
	int i=0;
	int j=0;
	for(i=0;i<curr_node;i++){
		network[i].visited=0;
	}
	i=getLoc(nodeID,network,curr_node);
	if(i==-1){
		return 0;
	}
		
	queue<int> Que[2];
	int currQ=0;

	Que[currQ].push(i);
	for(;TTL>=0;currQ^=1,TTL--){
		while(!Que[currQ].empty()){
			i=Que[currQ].front();
			Que[currQ].pop();
			network[i].visited=1;

			for(j=0;j<network[i].directConns;j++){
				if(!network[network[i].connectedTo[j]].visited)
					Que[currQ^1].push(network[i].connectedTo[j]);
			}
		}
	}
	
	for(i=0,j=0;i<curr_node;i++)
		j+=network[i].visited;

	return j;
}

int main(){

	cout.setf(ios::unitbuf);
	NODE network[30];
	
	int NC,casenum=1;
	int i;int curr_node;
	int t1,t2;
	
	while(1){
		cin>>NC;
		if(!NC)break;
		curr_node=0;

		for(i=0;i<NC;i++){
			cin>>t1>>t2;
			int loc1,loc2;
			loc1=getLoc(t1,network,curr_node);
			loc2=getLoc(t2,network,curr_node);

			if(loc1==-1){
				network[curr_node].NWID=t1;
				network[curr_node].directConns=0;
				network[curr_node].connectedTo[network[curr_node].directConns++]=(loc2==-1?curr_node+1:loc2);
				curr_node++;
			}
			else{
				network[loc1].connectedTo[network[loc1].directConns++]=(loc2==-1?curr_node:loc2);
			}
			if(t1==t2)continue;
			
			if(loc2==-1){
				network[curr_node].NWID=t2;
				network[curr_node].directConns=0;
				network[curr_node].connectedTo[network[curr_node].directConns++]=(loc1==-1?curr_node-1:loc1);
				curr_node++;
			}
			else{
				network[loc2].connectedTo[network[loc2].directConns++]=(loc1==-1?curr_node-1:loc1);
			}
		}

		while(1){
			cin>>t1>>t2;
			if(!t1&&!t2)
				break;

			i=countReachAbles(t1,t2,network,curr_node);
			cout<<"Case "<<casenum++<<": "<<curr_node-i<<" nodes not reachable from node "<<t1<<" with TTL = "<<t2<<".\n";
		}
	}
	return 0;
}

BTW why REs occur usually?
Thnx

[Darko]

That large I/O seems to be a little bit misleading, this is my diff file (note that is different from mf's... diff...):

Code: Select all

7,9c7,9
< Case 7: 5 nodes not reachable from node 35 with TTL = 2.
< Case 8: 1 nodes not reachable from node 35 with TTL = 3.
< Case 9: 12 nodes not reachable from node 1 with TTL = 3.
---
> Case 7: 6 nodes not reachable from node 35 with TTL = 2. 
> Case 8: 2 nodes not reachable from node 35 with TTL = 3. 
> Case 9: 13 nodes not reachable from node 1 with TTL = 3. 
15c15
< Case 15: 1 nodes not reachable from node 2 with TTL = 0.
---
> Case 15: 2 nodes not reachable from node 2 with TTL = 0. 
24,30c24,30
< Case 24: 4 nodes not reachable from node 1 with TTL = 1.
< Case 25: 6 nodes not reachable from node 1 with TTL = 0.
< Case 26: 5 nodes not reachable from node 4 with TTL = 1.
< Case 27: 5 nodes not reachable from node 4 with TTL = 2.
< Case 28: 5 nodes not reachable from node 5 with TTL = 1.
< Case 29: 5 nodes not reachable from node 6 with TTL = 2.
< Case 30: 5 nodes not reachable from node 8 with TTL = 2.
---
> Case 24: 5 nodes not reachable from node 1 with TTL = 1. 
> Case 25: 7 nodes not reachable from node 1 with TTL = 0. 
> Case 26: 6 nodes not reachable from node 4 with TTL = 1. 
> Case 27: 6 nodes not reachable from node 4 with TTL = 2. 
> Case 28: 6 nodes not reachable from node 5 with TTL = 1. 
> Case 29: 6 nodes not reachable from node 6 with TTL = 2. 
> Case 30: 7 nodes not reachable from node 8 with TTL = 2. 
147,153c147,153
< Case 147: 1 nodes not reachable from node 10 with TTL = 0.
< Case 148: 0 nodes not reachable from node 10 with TTL = 1.
< Case 149: 0 nodes not reachable from node 10 with TTL = 2.
< Case 150: 1 nodes not reachable from node 12 with TTL = 1.
< Case 151: 1 nodes not reachable from node 10 with TTL = 0.
< Case 152: 0 nodes not reachable from node 10 with TTL = 1.
< Case 153: 0 nodes not reachable from node 10 with TTL = 2.
---
> Case 147: 2 nodes not reachable from node 10 with TTL = 0. 
> Case 148: 1 nodes not reachable from node 10 with TTL = 1. 
> Case 149: 1 nodes not reachable from node 10 with TTL = 2. 
> Case 150: 2 nodes not reachable from node 12 with TTL = 1. 
> Case 151: 2 nodes not reachable from node 10 with TTL = 0. 
> Case 152: 1 nodes not reachable from node 10 with TTL = 1. 
> Case 153: 1 nodes not reachable from node 10 with TTL = 2.

I couldn't figure out what was wrong with it, so I submitted it. And it got AC. I noticed a lot of zeros there, I thought nodes were positive integers only?

[yasseryahia]

this is my answer for the test cases that CDiMa has put and my code is AC so I think those are the right answers

Code: Select all

Case 1: 5 nodes not reachable from node 35 with TTL = 2.
Case 2: 1 nodes not reachable from node 35 with TTL = 3.
Case 3: 8 nodes not reachable from node 1 with TTL = 1.
Case 4: 5 nodes not reachable from node 1 with TTL = 2.
Case 5: 3 nodes not reachable from node 3 with TTL = 2.
Case 6: 1 nodes not reachable from node 3 with TTL = 3.
Case 7: 5 nodes not reachable from node 35 with TTL = 2.
Case 8: 1 nodes not reachable from node 35 with TTL = 3.
Case 9: 13 nodes not reachable from node 1 with TTL = 3.
Case 10: 11 nodes not reachable from node 1 with TTL = 1.
Case 11: 8 nodes not reachable from node 1 with TTL = 2.
Case 12: 6 nodes not reachable from node 3 with TTL = 2.
Case 13: 4 nodes not reachable from node 3 with TTL = 3.
Case 14: 12 nodes not reachable from node 21 with TTL = 1.
Case 15: 2 nodes not reachable from node 2 with TTL = 0.
Case 16: 0 nodes not reachable from node 1 with TTL = 0.
Case 17: 3 nodes not reachable from node 1 with TTL = 5.
Case 18: 4 nodes not reachable from node 1 with TTL = 1.
Case 19: 3 nodes not reachable from node 4 with TTL = 2.
Case 20: 1 nodes not reachable from node 1 with TTL = 1.
Case 21: 0 nodes not reachable from node 1 with TTL = 2.
Case 22: 0 nodes not reachable from node 1 with TTL = 3.
Case 23: 3 nodes not reachable from node 1 with TTL = 0.
Case 24: 4 nodes not reachable from node 1 with TTL = 1.
Case 25: 6 nodes not reachable from node 1 with TTL = 0.
Case 26: 5 nodes not reachable from node 4 with TTL = 1.
Case 27: 5 nodes not reachable from node 4 with TTL = 2.
Case 28: 5 nodes not reachable from node 5 with TTL = 1.
Case 29: 5 nodes not reachable from node 6 with TTL = 2.
Case 30: 7 nodes not reachable from node 8 with TTL = 2.
Case 31: 4 nodes not reachable from node 2 with TTL = 3.
Case 32: 7 nodes not reachable from node 7 with TTL = 2.
Case 33: 7 nodes not reachable from node 10 with TTL = 1.
Case 34: 4 nodes not reachable from node 1 with TTL = 0.
Case 35: 3 nodes not reachable from node 1 with TTL = 1.
Case 36: 2 nodes not reachable from node 1 with TTL = 2.
Case 37: 2 nodes not reachable from node 1 with TTL = 3.
Case 38: 2 nodes not reachable from node 1 with TTL = 4.
Case 39: 4 nodes not reachable from node 2 with TTL = 0.
Case 40: 2 nodes not reachable from node 2 with TTL = 1.
Case 41: 2 nodes not reachable from node 2 with TTL = 2.
Case 42: 2 nodes not reachable from node 2 with TTL = 3.
Case 43: 2 nodes not reachable from node 2 with TTL = 4.
Case 44: 4 nodes not reachable from node 3 with TTL = 0.
Case 45: 3 nodes not reachable from node 3 with TTL = 1.
Case 46: 2 nodes not reachable from node 3 with TTL = 2.
Case 47: 2 nodes not reachable from node 3 with TTL = 3.
Case 48: 4 nodes not reachable from node 4 with TTL = 0.
Case 49: 4 nodes not reachable from node 4 with TTL = 1.
Case 50: 4 nodes not reachable from node 4 with TTL = 2.
Case 51: 29 nodes not reachable from node 1 with TTL = 0.
Case 52: 25 nodes not reachable from node 1 with TTL = 1.
Case 53: 21 nodes not reachable from node 1 with TTL = 2.
Case 54: 17 nodes not reachable from node 1 with TTL = 3.
Case 55: 13 nodes not reachable from node 1 with TTL = 4.
Case 56: 10 nodes not reachable from node 1 with TTL = 5.
Case 57: 8 nodes not reachable from node 1 with TTL = 6.
Case 58: 6 nodes not reachable from node 1 with TTL = 7.
Case 59: 4 nodes not reachable from node 1 with TTL = 8.
Case 60: 2 nodes not reachable from node 1 with TTL = 9.
Case 61: 0 nodes not reachable from node 1 with TTL = 10.
Case 62: 0 nodes not reachable from node 1 with TTL = 11.
Case 63: 0 nodes not reachable from node 1 with TTL = 12.
Case 64: 0 nodes not reachable from node 1 with TTL = 13.
Case 65: 0 nodes not reachable from node 1 with TTL = 14.
Case 66: 0 nodes not reachable from node 1 with TTL = 15.
Case 67: 0 nodes not reachable from node 1 with TTL = 16.
Case 68: 0 nodes not reachable from node 1 with TTL = 17.
Case 69: 0 nodes not reachable from node 1 with TTL = 18.
Case 70: 0 nodes not reachable from node 1 with TTL = 19.
Case 71: 0 nodes not reachable from node 1 with TTL = 20.
Case 72: 0 nodes not reachable from node 1 with TTL = 21.
Case 73: 29 nodes not reachable from node 18 with TTL = 0.
Case 74: 27 nodes not reachable from node 18 with TTL = 1.
Case 75: 25 nodes not reachable from node 18 with TTL = 2.
Case 76: 23 nodes not reachable from node 18 with TTL = 3.
Case 77: 19 nodes not reachable from node 18 with TTL = 4.
Case 78: 15 nodes not reachable from node 18 with TTL = 5.
Case 79: 11 nodes not reachable from node 18 with TTL = 6.
Case 80: 7 nodes not reachable from node 18 with TTL = 7.
Case 81: 5 nodes not reachable from node 18 with TTL = 8.
Case 82: 4 nodes not reachable from node 18 with TTL = 9.
Case 83: 3 nodes not reachable from node 18 with TTL = 10.
Case 84: 2 nodes not reachable from node 18 with TTL = 11.
Case 85: 1 nodes not reachable from node 18 with TTL = 12.
Case 86: 0 nodes not reachable from node 18 with TTL = 13.
Case 87: 0 nodes not reachable from node 18 with TTL = 14.
Case 88: 0 nodes not reachable from node 18 with TTL = 15.
Case 89: 29 nodes not reachable from node 1 with TTL = 0.
Case 90: 25 nodes not reachable from node 1 with TTL = 1.
Case 91: 21 nodes not reachable from node 1 with TTL = 2.
Case 92: 17 nodes not reachable from node 1 with TTL = 3.
Case 93: 13 nodes not reachable from node 1 with TTL = 4.
Case 94: 9 nodes not reachable from node 1 with TTL = 5.
Case 95: 6 nodes not reachable from node 1 with TTL = 6.
Case 96: 4 nodes not reachable from node 1 with TTL = 7.
Case 97: 2 nodes not reachable from node 1 with TTL = 8.
Case 98: 1 nodes not reachable from node 1 with TTL = 9.
Case 99: 0 nodes not reachable from node 1 with TTL = 10.
Case 100: 0 nodes not reachable from node 1 with TTL = 11.
Case 101: 0 nodes not reachable from node 1 with TTL = 12.
Case 102: 0 nodes not reachable from node 1 with TTL = 13.
Case 103: 0 nodes not reachable from node 1 with TTL = 14.
Case 104: 0 nodes not reachable from node 1 with TTL = 15.
Case 105: 0 nodes not reachable from node 1 with TTL = 16.
Case 106: 0 nodes not reachable from node 1 with TTL = 17.
Case 107: 0 nodes not reachable from node 1 with TTL = 18.
Case 108: 0 nodes not reachable from node 1 with TTL = 19.
Case 109: 0 nodes not reachable from node 1 with TTL = 20.
Case 110: 0 nodes not reachable from node 1 with TTL = 21.
Case 111: 29 nodes not reachable from node 18 with TTL = 0.
Case 112: 27 nodes not reachable from node 18 with TTL = 1.
Case 113: 25 nodes not reachable from node 18 with TTL = 2.
Case 114: 23 nodes not reachable from node 18 with TTL = 3.
Case 115: 19 nodes not reachable from node 18 with TTL = 4.
Case 116: 14 nodes not reachable from node 18 with TTL = 5.
Case 117: 8 nodes not reachable from node 18 with TTL = 6.
Case 118: 3 nodes not reachable from node 18 with TTL = 7.
Case 119: 1 nodes not reachable from node 18 with TTL = 8.
Case 120: 0 nodes not reachable from node 18 with TTL = 9.
Case 121: 0 nodes not reachable from node 18 with TTL = 10.
Case 122: 0 nodes not reachable from node 18 with TTL = 11.
Case 123: 0 nodes not reachable from node 18 with TTL = 12.
Case 124: 0 nodes not reachable from node 18 with TTL = 13.
Case 125: 0 nodes not reachable from node 18 with TTL = 14.
Case 126: 0 nodes not reachable from node 18 with TTL = 15.
Case 127: 4 nodes not reachable from node 1 with TTL = 0.
Case 128: 3 nodes not reachable from node 1 with TTL = 1.
Case 129: 2 nodes not reachable from node 1 with TTL = 2.
Case 130: 2 nodes not reachable from node 1 with TTL = 3.
Case 131: 4 nodes not reachable from node 2 with TTL = 0.
Case 132: 2 nodes not reachable from node 2 with TTL = 1.
Case 133: 2 nodes not reachable from node 2 with TTL = 2.
Case 134: 2 nodes not reachable from node 2 with TTL = 3.
Case 135: 4 nodes not reachable from node 3 with TTL = 0.
Case 136: 3 nodes not reachable from node 3 with TTL = 1.
Case 137: 2 nodes not reachable from node 3 with TTL = 2.
Case 138: 2 nodes not reachable from node 3 with TTL = 3.
Case 139: 4 nodes not reachable from node 4 with TTL = 0.
Case 140: 3 nodes not reachable from node 4 with TTL = 1.
Case 141: 3 nodes not reachable from node 4 with TTL = 2.
Case 142: 3 nodes not reachable from node 4 with TTL = 3.
Case 143: 4 nodes not reachable from node 5 with TTL = 0.
Case 144: 3 nodes not reachable from node 5 with TTL = 1.
Case 145: 3 nodes not reachable from node 5 with TTL = 2.
Case 146: 3 nodes not reachable from node 5 with TTL = 3.
Case 147: 1 nodes not reachable from node 10 with TTL = 0.
Case 148: 0 nodes not reachable from node 10 with TTL = 1.
Case 149: 0 nodes not reachable from node 10 with TTL = 2.
Case 150: 2 nodes not reachable from node 12 with TTL = 1.
Case 151: 2 nodes not reachable from node 10 with TTL = 0.
Case 152: 1 nodes not reachable from node 10 with TTL = 1.
Case 153: 1 nodes not reachable from node 10 with TTL = 2.

[Spykaj]

Code: Select all

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<stack>
#include<vector>
#include<set>
#include<queue>
#include<list>

using namespace std;

int Z,x,y,i,j,f=1,odp,K[51],n;
vector<int>V[51],pusty_vec;
set<int>L,pusty_set;
set<pair<int,int> > Y,pusty_set_par;

int pozycja(int x){
  int l = 0;
  for(set<int>::iterator s=L.begin(); s!=L.end(); s++){
    if(x == *s){
      return l;
    }
    l++;
  }
  return 0;
}

void bfs(int t,int poziom){
  /*for(int k=0; k<poziom; k++)printf("  ");
  printf("%d\n",t);*/
  if(K[t]==0 && poziom < y){
    K[t] = 1;
    odp--;
    for(vector<int>::iterator i=V[t].begin(); i!=V[t].end(); i++){
      if(K[*i]==0){
        /*if(poziom+1 >= y){
          if(K[*i]==0){
            K[*i]=1;
            odp--;
          }
        }*/
        //if(poziom+1 <= y)
        bfs(*i,poziom+1);
      }
    }
  }
  if(poziom >= y){
    if(K[t]==0){
      K[t]=1;
      odp--;
    }
  }
}

int main(){

  while(scanf("%d",&Z)&&Z){

    L = pusty_set;
    Y = pusty_set_par;

    for(i=0; i<Z; i++){
      scanf("%d%d",&x,&y);
      L.insert(x);
      L.insert(y);
      if(x>y)swap(x,y);
      Y.insert(pair<int,int>(x,y));
    }

    n = 0;
    for(set<int>::iterator s=L.begin(); s!=L.end(); s++){
      n++;
    }

    //printf("Jest %d wezlow\n",n);

    for(i=0; i<=n; i++){
      V[i] = pusty_vec;
    }

    for(set<pair<int,int> >::iterator sp=Y.begin(); sp!=Y.end(); sp++){
      V[pozycja((*sp).first)].push_back(pozycja((*sp).second));
      if((*sp).first != (*sp).second)
        V[pozycja((*sp).second)].push_back(pozycja((*sp).first));
    }

    /*for(i=0; i<n; i++){
      for(vector<int>::iterator j=V[i].begin(); j!=V[i].end(); j++){
        printf("%d ",*j);
      } printf("\n");
    }*/

    /*for(set<int>::iterator s=L.begin(); s!=L.end(); s++){
      printf("%2d ",*s);
    } printf("\n");*/

    while(scanf("%d%d",&x,&y)&&(x||y)){
      for(int i=0; i<=50; i++){
        K[i] = 0;
      }
      odp = n;
      bfs(pozycja(x),0);
      printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",f,odp,x,y);
      f++;
    }
  }

  return 0;

}

I don't searched any bad tests, but i still have WA plz help me !!!! I can't believe this.

[Jan]

Dont open a new thread if you find at least one. Try searching the existing threads first. If you do need to post then post in an existing thread.

[vinit_iiita]

Code: Select all

#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
struct edge{
       int x;
       int y;
       };
int main()
{
    int n;
    int q=1;
    while (cin>>n && n!=0)
    {
          vector< edge > v;
          for (int i=0;i<n;i++)
          {
              edge e;
              cin>>e.x>>e.y;
              v.push_back(e);
              }
              vector<int> vin;
           for (int i=0;i<v.size();i++)
           {
                int k=v[i].x;
                bool flag=true;
                for (int j=0;j<vin.size();j++)
                if (k==vin[j])
                {
                              flag=false;
                              break;
                              }
                if(flag)
                vin.push_back(k);
               flag=true;
                k=v[i].y;
                for (int j=0;j<vin.size();j++)
                if (k==vin[j])
                {
                              flag=false;
                              break;
                              }
                if(flag)
                vin.push_back(k);
                }
                
                int m,n;
                while (cin>>m>>n && !(m==0 && n==0))
                {
                     
              
                   vector<int> r;
                   r.push_back(m);
                   for (int w=0;w<n;w++)
                   {
                        
                       int h=r.size();
                       for (int j=0;j<h;j++)
                       {
                    
                       for (int i=0;i<v.size();i++)
                       {
                       if (v[i].x==r[j])
                       {bool fla=true;
                       for (int l=0;l<h;l++)
                       if(v[i].y==r[l])
                       {
                                       fla=false;
                                       break;
                                       }
                       if(fla)
                       r.push_back(v[i].y);
                       }
                       else if (v[i].y==r[j] )
                       {bool fla=true;
                       for (int l=0;l<h;l++)
                       if(v[i].x==r[l])
                       {
                                       fla=false;
                                       break;
                                       }
                       if(fla)
                       r.push_back(v[i].x);
                       }
                       }
                       }
                       }
                    int c=0;
                    for(int i=0;i<r.size();i++)
                    {
                    bool f=true;
                    for (int j=0;j<i;j++)  
                    if (r[i]==r[j])
                    f=false;
                    if (f)
                    c++;
                    }
                     cout<<"Case "<<q<<": "<<vin.size()-c<<" nodes not reachable from node "<<m<<" with TTL = "<<n<<".\n";   
            
                     q++;
                      }
             
              }
              return 0;
              }
               
          

plz..tell me why it is giving TLE its running quit fast and is giving correct output to above 153 cases..

[fidels]

just a note here:

this is my answer for the test cases that CDiMa has put and my code is AC so I think those are the right answers

Code: Select all

...
Case 147: 1 nodes not reachable from node 10 with TTL = 0.
Case 148: 0 nodes not reachable from node 10 with TTL = 1.
Case 149: 0 nodes not reachable from node 10 with TTL = 2.
Case 150: 2 nodes not reachable from node 12 with TTL = 1.
Case 151: 2 nodes not reachable from node 10 with TTL = 0.
Case 152: 1 nodes not reachable from node 10 with TTL = 1.
Case 153: 1 nodes not reachable from node 10 with TTL = 2.

the last three answers are not quite right there. the test case said:

Code: Select all

1
10 11
10 0 10 1 10 2 12 1 10 0 10 1 10 2 0 0
0

so questions 147, 148 and 149 are exactly the same as 151, 152 and 153, yet they yield different answers. the correct ones are the ones in 147, 148 and 149, so it should read:

Code: Select all

Case 147: 1 nodes not reachable from node 10 with TTL = 0.
Case 148: 0 nodes not reachable from node 10 with TTL = 1.
Case 149: 0 nodes not reachable from node 10 with TTL = 2.
Case 150: 2 nodes not reachable from node 12 with TTL = 1.
Case 151: 1 nodes not reachable from node 10 with TTL = 0.
Case 152: 0 nodes not reachable from node 10 with TTL = 1.
Case 153: 0 nodes not reachable from node 10 with TTL = 2.

[Mushfiqur Rahman]

Can there be any node in the input set whose value is more than 2^31-1. If not, then whats the problem with this code. I checked it but didn't found any mistake.

Code: Select all

Removed after AC.

Important for others:

No, theres no node which value is more than 2^31-1, but there can be more than 30 nodes

I getting WA for many times.