336 - A Node Too Far

[brianfry713]

http://www.uvatoolkit.com/problemssolve.php

[sandrela]

Thanks. i just skipped the line "After each block there is one empty line."

[t_ton123]

16
10 15 15 20 20 25 10 30 30 47 47 50 25 45 45 65
15 35 35 55 20 40 50 55 35 40 55 60 40 60 60 65
35 2 35 3 1 3 0 0

For this input why does this input give the output 3 nodes when it should be 13 nodes since 12 is not connected to the others?

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 : 3 nodes not reachable from node 1 with TTL = 3 //this one

[lbv]

For this input why does this input give the output 3 nodes when it should be 13 nodes since 12 is not connected to the others?

My AC code does print 13 for that query. If other AC programs print something different, it's probably because the judge's data sets don't contain cases like that (with queries about nodes that are not listed in the connections).

[brianfry713]

My AC output for your input:

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: 13 nodes not reachable from node 1 with TTL = 3.

[Shihab]

help rte

Code: Select all

#include<map>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
#define max 1
using namespace std;

//printf("%llu\n",~1+1);
//FILE *op = fopen("Input.txt","r");
//op=fopen("Output.txt","w");
//map<long long,long long>result;
//map<int,int>:: iterator u;
queue<long long>nodes;
vector<long long>graph[1000];

void bfs( long long source,long long  l  )
{
    long long visited[1000] = { 0 },level[1000],parent[1000];
    long long g,h,i;
    int not_reachable  = 0;

    level[source] = 0;
    visited[source] = 1;
    nodes.push( source );
    //h  = source;
    while( !nodes.empty() )
    {
        h = nodes.front();
        for( i = 0 ; i < graph[ h ].size(); i++ )
        {
            g = graph[ h ][ i ];
            if( !visited[ g ] )
            {
                //printf("%d %d\n",h,g);
                level[ g ] =  level[ h ] + 1;
                if( level[g] > l )
                    ++not_reachable;
                visited[g] = 1;
                nodes.push( g );
            }
        }
        //graph[ h ].clear( );
        nodes.pop();
    }
    printf("%d nodes not reachable from node %lld with TTl = %lld.\n",not_reachable,source,l );

}

int main()
{
    long long t,i,u,v,source,l,casse = 0,j;
    while( scanf("%lld",&t),t!=0 )
    {
        i = 1;

        while( i <= t )
        {
            scanf("%lld %lld",&u,&v);
            graph[ u ].push_back( v );
            graph[ v ].push_back( u );
            i++;
        }
        //source = 1,level =1;
        while( scanf("%lld %lld",&source,&l ) )
        {
            if( source == 0 && l == 0 )
                break;
            printf("Case %lld: ",++casse);
            bfs( source,l );

        }
        for( j = 0; j < 1000; j++ )
            graph[ j ].clear();
    }
    return 0;
}

[poet]

Could you guys please help me out with my code?
My program seems to generate all the right outputs for the given inputs on this forum.
However, I am getting WA again and again. I used BFS, and created a struct for node.

MY code:

#include <iostream>
#include <fstream>
#include <queue>
#define MAX_NODE_IN_NETWORK 100
#define NOT_PRESENT -1
#define PSEUDO_INFINITY 1000000000
using namespace std;

long long case_number=1;
long long error_number=-9;
struct node{
long long node_value;
//list of neighbors
long long neighbors[MAX_NODE_IN_NETWORK];
long long number_of_neighbors;
bool is_explored;
long long distance_from_source;
bool is_cycled;
};
node nodes[MAX_NODE_IN_NETWORK];
queue<node> bfs_queue;
void reset_nodes(){
for(long long i=0;i<MAX_NODE_IN_NETWORK;i++){
nodes.node_value=NOT_PRESENT;
nodes.number_of_neighbors=0;
nodes.is_explored=false;
nodes.is_cycled=false;
nodes.distance_from_source=PSEUDO_INFINITY;
for(long long j=0;j<MAX_NODE_IN_NETWORK;j++){
nodes.neighbors[j]=NOT_PRESENT;
}
}
}

long long index_of_node_in_array(long long node){
for(long long i=0;i<MAX_NODE_IN_NETWORK;i++){
if(nodes.node_value==node)
return i;
}
return NOT_PRESENT;
}
long long first_available_index_of_array(){
for(long long i=0;i<MAX_NODE_IN_NETWORK;i++){
if(nodes.node_value==NOT_PRESENT)
return i;
}
return NOT_PRESENT;
}

void display_nodes(){
cout<<endl<<"Displaying nodes"<<endl;
long long max=first_available_index_of_array();
for(long long i=0;i<max;i++){
if(nodes.node_value!=NOT_PRESENT)
cout<<nodes.node_value<<": ";
long long size=nodes[i].number_of_neighbors;
for(long long j=0;j<size;j++){
cout<<nodes[i].neighbors[j]<<", ";
}
cout<<endl;
}
}


long long solve_and_return_number_of_unexplored_nodes(long long starting_node, long long ttl){
long long k=0;
for(long long i=0;i<MAX_NODE_IN_NETWORK;i++){
if(nodes[i].node_value!=NOT_PRESENT) k++;

}
//now, we have to run BFS on the data
long long index_of_starting_node=index_of_node_in_array(starting_node);
if (index_of_starting_node==NOT_PRESENT) {
return k;
}
nodes[index_of_starting_node].is_explored=true;
nodes[index_of_starting_node].distance_from_source=0;
bfs_queue.push(nodes[index_of_starting_node]);
//cout<<endl<<"BFS MAN BFS"<<endl;
while(!bfs_queue.empty()){
node v=bfs_queue.front();
//cout<<"exploring node "<<v.node_value<<endl;
bfs_queue.pop();

//for each edge (v, w)
long long neighbors_count=v.number_of_neighbors;
//cout<<"unexplored neighbors: ";
for(long long i=0;i<neighbors_count;i++){
//if w is unexplored
//mark it as explored
//add it to bfs_queue
long long w_index=index_of_node_in_array((v.neighbors[i]));
if(!nodes[w_index].is_explored && nodes[w_index].node_value!=NOT_PRESENT){
nodes[w_index].is_explored=true;
nodes[w_index].distance_from_source=v.distance_from_source+1;
bfs_queue.push(nodes[w_index]);
//cout<<nodes[index_of_node_in_array((v.neighbors[i]))].node_value<<", ";
}

}
}
long long count=0;
for(long long i=0;i<MAX_NODE_IN_NETWORK;i++){
if(nodes[i].node_value!=NOT_PRESENT && nodes[i].distance_from_source>ttl)
count++;
}
return count;
}
void set_nodes_unexplored(){
for(long long i=0;i<MAX_NODE_IN_NETWORK;i++){
nodes[i].is_explored=false;
nodes[i].distance_from_source=PSEUDO_INFINITY;
}
}
void node_solve (std::istream& in, std::ostream& out) {
long long n;

while((in>>n) && n!=0){
reset_nodes();
long long a, b;
for(long long i=0;i<n;i++){
in>>a;
in>>b;
long long index_of_node_a;
long long index_of_node_b;
if(a!=b){
if((index_of_node_a=index_of_node_in_array(a))!=NOT_PRESENT){
//easy part
long long new_index=nodes[index_of_node_a].number_of_neighbors;
nodes[index_of_node_a].neighbors[new_index]=b;
nodes[index_of_node_a].number_of_neighbors=nodes[index_of_node_a].number_of_neighbors+1;
}
else{
//hard part
long long available_index=first_available_index_of_array();
nodes[available_index].node_value=a;
//the first neighbor
nodes[available_index].neighbors[0]=b;
//has merely one neighbor
nodes[available_index].number_of_neighbors=1;
}
if((index_of_node_b=index_of_node_in_array(b))!=NOT_PRESENT){
//easy part
long long new_index=nodes[index_of_node_b].number_of_neighbors;
nodes[index_of_node_b].neighbors[new_index]=a;
nodes[index_of_node_b].number_of_neighbors=nodes[index_of_node_b].number_of_neighbors+1;
}
else{
//hard part
long long available_index=first_available_index_of_array();
nodes[available_index].node_value=b;
//the first neighbor
nodes[available_index].neighbors[0]=a;
//has merely one neighbor
nodes[available_index].number_of_neighbors=1;
}
}
else{
//hard part
long long available_index=first_available_index_of_array();
nodes[available_index].node_value=a;
//has merely one neighbor
nodes[available_index].number_of_neighbors=0;
}
}

long long starting_node;
long long ttl;
//display_nodes();
//now we read in pairs of nodes, which stop when we hit "0 0"
while((in>>starting_node) && starting_node!=0){
//if(case_number!=1) out<<endl;
set_nodes_unexplored();
bfs_queue=queue<node>();
in>>ttl;
//Case 1: 5 nodes not reachable from node 35 with TTL = 2.
//Case 1: 5 nodes not reachable from node 35 with TTL = 2.
// if(case_number==error_number)
// out<<"n: "<<n<<": node "<<starting_node<<" "<<ttl<<endl;
out<<"Case "<<case_number<<": "<<solve_and_return_number_of_unexplored_nodes(starting_node, ttl)<<" nodes not reachable from node "<<starting_node<<" with TTL = "<<ttl<<"."<<endl;
case_number++;
}
//reading the second zero
in>>ttl;
//emptying the queue

}


}
int main(){

node_solve(cin, cout);
return 0;
}

[brianfry713]

Shihab, The node numbers can be any integer, maybe greater than 1000, use a map.

[brianfry713]

poet, try this:

Input:

Code: Select all

16
10 15  15 20  20 25  10 30  30 47  47 50  25 45  45 65
15 35  35 55  20 40  50 55  35 40  55 60  40 60  60 65
35  2  35  3   0  0

14
1 2  2 7  1 3  3 4  3 5  5 10  5 11
4 6  7 6  7 8  7 9  8 9  8  6  6 11
1 1  1 2  3 2  3 3  0 0
16
10 15  15 20  20 25  10 30  30 47  47 50  25 45  45 65
15 35  35 55  20 40  50 55  35 40  55 60  40 60  60 65
35  2  35  3   1  3   0  0

16
1 2  2 7  1 3  3 4  3 5  5 10  5 11
4 6  7 6  7 8  7 9  8 9  8  6  6 11 21 22 22 23
1 1  1 2  3 2  3 3  21 1 0 0

1
1 3
2 0
0 0

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

4
1 2
2 3
3 4
1 4
1 1
1 2
1 3
1 0
0 0


5
1 2 2 3 3 1 4 5 6 2147483647
1 1 1 0 4 1 4 2 5 1 6 2 8 2 0 0

10
1 2 1 3 3 5 2 5 3 4 5 4 6 4 7 10 10 9 8 9
2 3 7 2 10 1 0 0
 
4
0 0 1 2 2 3 4 4
1 0 1 1 1 2 1 3 1 4 2 0 2 1 2 2 2 3 2 4 3 0 3 1 3 2 3 3 4 0 4 1 4 2
0 0
 
30
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 0 0 1
11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 1
21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 1
1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16
1 17 1 18 1 19 1 20 1 21 18 0 18 1 18 2 18 3 18 4 18 5 18 6 18 7 18 8 18 9
18 10 18 11 18 12 18 13 18 14 18 15 0 0
32
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 0 0 1 5 14 24 13
11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 1
21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 1
1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16
1 17 1 18 1 19 1 20 1 21 18 0 18 1 18 2 18 3 18 4 18 5 18 6 18 7 18 8 18 9
18 10 18 11 18 12 18 13 18 14 18 15 0 0
3
1 2 2 3 4 5
1 0 1 1 1 2 1 3 2 0 2 1 2 2 2 3 3 0 3 1 3 2 3 3 4 0 4 1 4 2 4 3 5 0 5 1 5 2 5 3
0 0
 
1
10 11
10 0 10 1 10 2 12 1 10 0 10 1 10 2 0 0
0

Correct output:

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: 3 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: 1 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: 4 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: 0 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.

[Knighteee]

I found where the problem.
it's in "336 - A Node Too Far"



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


1. when you get RE
possible reasons:
if you take all node in map, sometimes uva give unknown node as source node in test cases like 12 1
and if you try to get access with 12
your_map.at(12) you will get Run time error RE.

2. when you get WA
you get unknown node in test case
you have to add any unknown node to your network and increase network node number.
like above for 10 0 1 nodes not reachable from node 10 with TTL = 0.
and for 12 0 2 nodes not reachable from node 12 with TTL = 0.
now you have to add 12 as a new node to the network ,
so now for 10 0 2 nodes not reachable from node 10 with TTL = 0.

[ehsanulbigboss]

Getting Runtime Error:

Code: Select all

Thanks to brianfry713

[cse dipto]

AC thnks @brianfry713

[brianfry713]

cse dipto:
Input:

Code: Select all

3
1 2 1 1 2 3
1 0 1 1 1 2 0 0

0

AC output:

Code: Select all

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

I solved it by pushing the node number and TTL onto the queue.

[brianfry713]

ehsanulbigboss, TTL may be larger than 41.

[Ishtiaq11]

Runtime Error
My codes output is right for input given here. But why RE. Please help.

Code: Select all

/*+++++++++++++++++++++++++++++++++++++++++++
    @Name:  Ishtiaq Pias
    @Status: Not Accepted
    @Description:
    @Date:

+++++++++++++++++++++++++++++++++++++++++++++*/


#include<bits/stdc++.h>
using namespace std;

///==============[ Definings Here ]========================

#define sc              scanf
#define pr              printf
#define mx              1000009          //====[10^6]====
#define PI              acos(-1)
#define pb              push_back
#define ll              long long
#define NN              100000000        //===[10^8]====

#define readInt(a)      sc("%d",&a)
#define readChar(a)     sc("%c",&a)
#define readString(a)   sc("%s",&a)
#define readLong(a)     sc("%lld",&a)

#define FOR(a,b)        for(int i=a;i<b;i++)
#define ROF(a,b)        for(int i=a;i>=b;i--)
#define readLong2(a,b)  sc("%lld %lld",&a,&b)


///==============[Global Variables & Declared Functions Here]================


ll reachable_nodes(ll src,vector<ll> G[60],ll ttl)
{
    queue<ll>Q;
    vector<ll>level[60];
    ll lev[60]={0};
    Q.push(src);

    ll visited[60]= {0};
    visited[src]=1;
    lev[src]=0;
    level[lev[src]].pb(src);

    while(!Q.empty()) {
        ll u=Q.front();
//        pr("FRONT=%lld\n",u);
        for(ll i=0; i<G[u].size(); i++) {
            ll v=G[u][i];

            if(!visited[v]) {
                lev[v]=lev[u]+1;
                level[lev[v]].pb(v);
                visited[v]=1;
                Q.push(v);
            }
        }
        Q.pop();
    }
    ll cnt=1;
    for(ll i=1;i<=ttl;i++){
        cnt += level[i].size();
    }
    return cnt;

}

///=====================================[Main]===========================================
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    ll tc,i,nc,e,x,y,cs=0;

    while(cin>>nc) {
        if(!nc)  break;

        vector<ll>edge[60],n1,n2;
        set<ll>node;

        /*take edges*/
        for(i=0; i<nc; i++) {
            cin>>x>>y;
            n1.pb(x);
            n2.pb(y);
            node.insert(x);
            node.insert(y);
        }

        set<ll> :: iterator it;
        map<ll,ll>mp;
        i=0;

        for(it=node.begin();it!=node.end();it++){
            mp[*it]=i;
            i++;
        }

        for(i=0;i<n1.size();i++){
            x=mp[ n1[i] ];
            y=mp[ n2[i] ];
            edge[x].pb(y);
            edge[y].pb(x);
        }

//        for(it=node.begin();it!=node.end();it++){
//            pr("%lld ===> %lld\n",*it,mp[*it]);
//        }

        ll ttl,src;
        while(cin>>src>>ttl){
            if(!src && !ttl)    break;
            ll rcbl=reachable_nodes(mp[src],edge,ttl);
            ll ans=node.size()-rcbl;
            pr("Case %lld: %lld nodes not reachable from node %lld with TTL = %lld.\n",++cs,ans,src,ttl);
        }


    }

    return 0;
}