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

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

Re: 336

Post by brianfry713 » Fri Nov 15, 2013 9:16 pm

Check input and AC output for thousands of problems on uDebug!

sandrela
New poster
Posts: 1
Joined: Mon Jan 27, 2014 12:30 pm

Re: 336

Post by sandrela » Mon Jan 27, 2014 12:43 pm

Thanks. i just skipped the line "After each block there is one empty line."
CompTIA updated this exam literally a few days ago, so I am very impressed to see it here at 640-864 for more detail this product visit this main site Braindumps For more information about this product visit Youtube and also visit LSI ,best of luck.

t_ton123
New poster
Posts: 1
Joined: Sun Jul 20, 2014 7:10 pm

Re: 336 WA

Post by t_ton123 » Sun Jul 20, 2014 7:15 pm

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
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 336 WA

Post by lbv » Sun Jul 20, 2014 8:21 pm

t_ton123 wrote: 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 336 WA

Post by brianfry713 » Mon Jul 21, 2014 8:16 pm

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.
Check input and AC output for thousands of problems on uDebug!

Shihab
New poster
Posts: 33
Joined: Thu Jun 13, 2013 1:19 pm

Re: 336 - A Node Too Far

Post by Shihab » Mon Sep 29, 2014 8:28 pm

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
New poster
Posts: 1
Joined: Tue Sep 30, 2014 5:47 am

Re: 336 - A Node Too Far

Post by poet » Tue Sep 30, 2014 5:52 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 336 WA

Post by brianfry713 » Tue Sep 30, 2014 2:49 pm

Shihab, The node numbers can be any integer, maybe greater than 1000, use a map.
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 Sep 30, 2014 3:44 pm

poet, try this:
brianfry713 wrote: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.
Check input and AC output for thousands of problems on uDebug!

Knighteee
New poster
Posts: 1
Joined: Wed Oct 08, 2014 10:46 am

Re: 336 - A Node Too Far

Post by Knighteee » Wed Oct 08, 2014 11:01 am

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
New poster
Posts: 32
Joined: Tue Jul 22, 2014 1:17 am

Re: 336 - A Node Too Far

Post by ehsanulbigboss » Thu Jan 01, 2015 6:30 pm

Getting Runtime Error:

Code: Select all

Thanks to brianfry713
Last edited by ehsanulbigboss on Mon Jan 12, 2015 3:51 pm, edited 1 time in total.

cse dipto
New poster
Posts: 22
Joined: Tue Oct 29, 2013 6:46 pm

Re: 336 - A Node Too Far got WA!! plzz Help anyone Plzzz

Post by cse dipto » Sun Jan 04, 2015 9:38 pm

AC thnks @brianfry713
Last edited by cse dipto on Wed Jan 07, 2015 12:51 pm, edited 2 times in total.

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

Re: 336 - A Node Too Far

Post by brianfry713 » Wed Jan 07, 2015 1:16 am

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.
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 - A Node Too Far

Post by brianfry713 » Wed Jan 07, 2015 1:19 am

ehsanulbigboss, TTL may be larger than 41.
Check input and AC output for thousands of problems on uDebug!

Ishtiaq11
New poster
Posts: 2
Joined: Sat Sep 27, 2014 8:11 pm

Re: 336 - A Node Too Far

Post by Ishtiaq11 » Sun May 10, 2015 4:58 pm

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

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;
}

Post Reply

Return to “Volume 3 (300-399)”