10459 - The Tree Root

prashantharshi · Post by **prashantharshi** » Wed May 21, 2014 10:22 am

i m getting WA contnuously even my code print correct answers
need help
#include<iostream>
#define max 5100
#define size 5100
int pred[max];
int status[max];
int height[max];
int state[max];
using namespace std;
struct node
{
int data;
node* link;
node(int d)
{
data=d;
link=NULL;
}
};
struct lnode
{
int d;
node* right;
lnode* down;
lnode(int k)
{
d=k;
right=NULL;
down=NULL;
}
};

struct tnode
{
int data;
int no;
int flag;
tnode** childlist;
tnode(int d)
{
data=d;
no=0;
flag=0;
}
};
struct stack
{
tnode* arr[size];
int top;
void push(tnode*);
tnode* pop();
stack()
{
top=-1;
}
}st;
void stack::push(tnode* ptr)
{
arr[++top]=ptr;
}
tnode* stack::pop()
{
tnode* p1=arr[top];
top--;
return p1;
}
struct queue
{
int front;
int rear;
tnode* arr[size];
void insert(tnode*);
tnode* del();
queue();
}q;
queue::queue()
{
front=-1;
rear=-1;
}
tnode* queue::del()
{

if(front!=-1)
{
tnode* f=arr[front];
if(front==rear)
{
front=-1;
rear=-1;
}
else
{
front=(front+1)%size;
}
return f;
}

}
void queue::insert(tnode* f)
{
rear=(rear+1)%size;
arr[rear]=f;
if(front==-1)
front=0;
}

void fun(tnode* &root,int v,int n)
{
if(!root)
{
root=new tnode(v);
}
int loc[max];
int k,cnt;
k=cnt=0;
for(int i=1;i<=n;i++)
{
if(pred==v)
{
loc[k]=i;
cnt++;
k++;
}
}
root->no=cnt;
root->childlist=new tnode*[cnt];
for(int i=0;i<cnt;i++)
{
root->childlist=NULL;;
}
for(int i=0;i<cnt;i++)
{
fun(root->childlist,loc,n);
}
}
void replicate(tnode* root,tnode* &ptr)
{
if(!ptr)
{
ptr=new tnode(root->data);
ptr->no=root->no;
ptr->childlist=new tnode*[ptr->no];
for(int i=0;i<ptr->no;i++)
{
ptr->childlist=NULL;
}
}
for(int i=0;i<ptr->no;i++)
{
replicate(root->childlist,ptr->childlist);
}

}
int cnt_ancestor(tnode* root,int k,int &cnt)
{
int k1;
if(root->data==k)
{
root->flag=1;
return 1;
}
for(int i=0;i<root->no;i++)
{
k1=cnt_ancestor(root->childlist,k,cnt);
if(k1)
{
root->flag=1;
cnt++;
return 1;
}
}
return 0;
}
tnode* make_root(tnode* root,int cnt)
{
if(cnt==0)
return root;
tnode* ptr;
int p,ind,i;
while(cnt!=0)
{
for(i=0;i<root->no;i++)
{
if(root->childlist->flag==1)
{
ind=i;
ptr=root->childlist;
}
}
for(i=0;i<ptr->no;i++)
{
q.insert(ptr->childlist[i]);
}
p=ptr->no;
ptr->no++;
ptr->childlist=new tnode*[ptr->no];
for(i=0;i<p;i++)
{
ptr->childlist[i]=q.del();
}
ptr->childlist[i]=root;
for(i=ind;i<(root->no)-1;i++)
{
root->childlist[i]=root->childlist[i+1];
}
root->childlist[i]=NULL;
root->no--;
root->flag=0;
root=ptr;
cnt--;
}
return ptr;
}
void display(tnode* root)
{
if(root->no==0)
{
cout<<root->data<<" ";
return;
}
else
{
cout<<root->data<<" ";
for(int i=0;i<root->no;i++)
{
display(root->childlist[i]);
}
}
}
int get_height(tnode* root)
{
int m=0;
if(root->no==0)
{
return 0;
}
else
{
for(int i=0;i<root->no;i++)
{
int k=1+get_height(root->childlist[i]);
if(k>m)
m=k;
}
}
return m;
}
lnode* addafter1(lnode* start,int d)
{
if(start==NULL)
{
start=new lnode(d);
return start;
}
lnode* temp=start;
while(temp->down!=NULL)
{
temp=temp->down;
}
temp->down=new lnode(d);
return start;
}
node* addafter2(node* strt,int d)
{
if(strt==NULL)
{
strt=new node(d);
return strt;
}
node* temp=strt;
while(temp->link!=NULL)
{
temp=temp->link;
}
temp->link=new node(d);
return strt;
}
lnode* get_address(lnode* start,int v)
{
lnode* temp=start;
while(temp->d!=v)
{
temp=temp->down;
}
return temp;
}
void dfs(lnode* start,int v)
{
state[v]=1;
lnode* ptr=get_address(start,v);
node* temp=ptr->right;
while(temp!=NULL)
{
int p=temp->data;
if(state[p]==0)
{
pred[p]=v;
dfs(start,p);
}
temp=temp->link;
}
}
int main()
{
lnode* start=NULL;
int n,p,k,cnt;
int bh=999999;
int wh=-9999;
tnode** ptr;
tnode* root=NULL;
lnode* temp;
cin>>n;
ptr=new tnode*[n+1];
for(int i=1;i<=n;i++)
{
ptr[i]=NULL;
pred[i]=-1;
status[i]=0;
state[i]=0;
}
for(int i=1;i<=n;i++)
{
start=addafter1(start,i);
temp=start;
while(temp->down!=NULL)
{
temp=temp->down;
}
cin>>p;
for(int j=0;j<p;j++)
{
cin>>k;
temp->right=addafter2(temp->right,k);
}
}
dfs(start,1);
fun(root,1,n);
for(int i=1;i<=n;i++)
{
replicate(root,ptr[i]);
cnt=0;
int c=cnt_ancestor(ptr[i],i,cnt);
ptr[i]=make_root(ptr[i],cnt);
height[i]=get_height(ptr[i]);

}
for(int i=1;i<=n;i++)
{
if(height[i]<bh)
{
bh=height[i];
}
}
cout<<"Best Roots : ";
for(int i=1;i<=n;i++)
{
if(height[i]==bh)
cout<<i<<" ";
}
cout<<"\n";
for(int i=1;i<=n;i++)
{
if(height[i]>wh)
{
wh=height[i];
}
}
cout<<"Worst Roots : ";
for(int i=1;i<=n;i++)
{
if(height[i]==wh)
cout<<i<<" ";
}
return 0;

}

prashantharshi · Post by **prashantharshi** » Wed May 21, 2014 12:30 pm

here is my revised code using just dfs on adjacency list and getting the maximum depth during dfs as the height when that vertex act as root
my code is giving perfect outupts stiil verdict is WA
need urgent help
#include<iostream>
#define max 5100
int state[max];
int height[max];
using namespace std;
struct node
{
int data;
node* link;
node(int d)
{
data=d;
link=NULL;
}
};
struct lnode
{
int d;
node* right;
lnode* down;
lnode(int k)
{
d=k;
right=NULL;
down=NULL;
}
};

lnode* addafter1(lnode* start,int d)
{
if(start==NULL)
{
start=new lnode(d);
return start;
}
lnode* temp=start;
while(temp->down!=NULL)
{
temp=temp->down;
}
temp->down=new lnode(d);
return start;
}
node* addafter2(node* strt,int d)
{
if(strt==NULL)
{
strt=new node(d);
return strt;
}
node* temp=strt;
while(temp->link!=NULL)
{
temp=temp->link;
}
temp->link=new node(d);
return strt;
}
lnode* get_address(lnode* start,int v)
{
lnode* temp=start;
while(temp->d!=v)
{
temp=temp->down;
}
return temp;
}
void reset_status(int n)
{
for(int i=1;i<n;i++)
{
state=0;
}
}
void dfs(lnode* start,int v,int h,int &m)
{
state[v]=1;
lnode* ptr=get_address(start,v);
node* temp=ptr->right;
while(temp!=NULL)
{
int p=temp->data;
if(state[p]==0)
{
dfs(start,p,h+1,m);
}
temp=temp->link;
}
if(h>m)
m=h;
}
int main()
{
lnode* start=NULL;
int h,m,n,p,k;
int bh=999999;
int wh=-9999;
lnode* temp;
cin>>n;
for(int i=1;i<=n;i++)
{
start=addafter1(start,i);
temp=start;
while(temp->down!=NULL)
{
temp=temp->down;
}
cin>>p;
for(int j=0;j<p;j++)
{
cin>>k;
temp->right=addafter2(temp->right,k);
}
}
for(int i=1;i<=n;i++)
{
h=0,m=0;
reset_status(n);
dfs(start,i,h,m);
height=m;
}
for(int i=1;i<=n;i++)
{
if(height<bh)
{
bh=height;
}
}
cout<<"Best Roots : ";
for(int i=1;i<=n;i++)
{
if(height==bh)
cout<<i<<" ";
}
cout<<"\n";
for(int i=1;i<=n;i++)
{
if(height>wh)
{
wh=height;
}
}
cout<<"Worst Roots : ";
for(int i=1;i<=n;i++)
{
if(height==wh)
cout<<i<<" ";
}
return 0;

}

brianfry713 · Post by **brianfry713** » Wed May 21, 2014 8:29 pm

I ran your code on the sample input. Your code is printing:

Code: Select all

Best Roots : 1 
Worst Roots : 4 5 6 7

You also have an extra space at the end of each line. The correct sample output is:

Code: Select all

Best Roots  : 1
Worst Roots : 4 5 6 7

Use the code blocks when posting code.

piyukr · Post by **piyukr** » Sat Jul 26, 2014 1:14 pm

How to find the best roots for this problem?

lighted · Post by **lighted** » Wed Jul 30, 2014 10:02 pm

Sample Output

Best Rootsbb: 1
Worst Rootsb: 4 5 6 7

b is space.

brianfry713 wrote:Input:
Code: Select all
7
2 2 3
3 1 6 7
3 1 4 5
1 3
1 3
1 2
1 2
7
2 2 3
3 1 6 7
3 1 4 5
1 3
1 3
1 2
1 2
Output should be:
Code: Select all
Best Roots : 1
Worst Roots : 4 5 6 7
Best Roots : 1
Worst Roots : 4 5 6 7

brianfry713 wrote:I ran your code on the sample input. Your code is printing:
Code: Select all
Best Roots : 1 
Worst Roots : 4 5 6 7 
You also have an extra space at the end of each line. The correct sample output is:
Code: Select all
Best Roots  : 1
Worst Roots : 4 5 6 7
Use the code blocks when posting code.

They differ in one space after Best Roots. Is sample output correct?

brianfry713 · Post by **brianfry713** » Thu Jul 31, 2014 10:30 pm

The sample output is correct, there should be two spaces after Best Roots. I edited my previous post.

lighted · Post by **lighted** » Fri Aug 01, 2014 5:13 am

piyukr wrote:How to find the best roots for this problem?

The way how I find best roots:
1. Do loop while nodes exits
2. In each step delete all nodes that have only one parrent.
3. Nodes which remain at last are best roots.

I read that in a tree remain 1 or 2 node. As i understood they are called centers of tree(or graph).

I joined input given in this thread.

Code: Select all

Acc output

Code: Select all

Best Roots  : 1
Worst Roots : 4 5 6 7
Best Roots  : 6
Worst Roots : 3 4 7
Best Roots  : 1 2
Worst Roots : 6 7 8 9
Best Roots  : 1 4
Worst Roots : 5 7 8
Best Roots  : 1
Worst Roots : 4 5 6 7

Farsan · Post by **Farsan** » Sat Sep 06, 2014 1:42 pm

Is the given tree connected or could there be any forest???Getting Wa... Passed all I/O of the forum when the tree is connected,here is my code

Code: Select all

//ACED

lighted · Post by **lighted** » Sat Sep 06, 2014 5:35 pm

Your program doen't pass second test posted above.

Input

Code: Select all

Acc Output

Code: Select all

Best Roots  : 6
Worst Roots : 3 4 7

Your Output

Code: Select all

Best Roots  : 1 2 3 4 5 6 7 8
Worst Roots :

Farsan · Post by **Farsan** » Sat Sep 06, 2014 9:42 pm

That's why i asked whether is it possible that there is a forest instead of a tree in input.Even your output differs from the output i got herehttp://www.udebug.com/UVa/10459... I do not think there is any input where any node is isolated.

lighted · Post by **lighted** » Sun Sep 07, 2014 9:26 pm

Yes, you are right. According to problem description

Then successively for each i'th node there will be a positive integer K following id of K nodes which are adjacent to i

I added 1st and 2nd node to the tree. Try input

Code: Select all

Acc. Output

Code: Select all

Best Roots  : 6
Worst Roots : 1 2 3 4 7

Your Output

Code: Select all

Best Roots  : 6
Worst Roots : 2 7

Output of forthright48 (uDebug)

Code: Select all

Best Roots  : 5
Worst Roots : 1 3 4

Sometimes it happens that we get accepted for partial solutions. It is because judge's input are weak and may not contain all critical input.
forthright48's solution at uDebug for problem 11428 was changed because it wasn't giving correct answers for some critical input, though it was accepted by judge.
It was changed to brianfry713's solution.

brianfry713 · Post by **brianfry713** » Tue Sep 09, 2014 11:27 pm

I uploaded my code and some small random input to:
http://www.udebug.com/UVa/10459
Farsan, your code fails some of those random input cases.

The judge's input only contains trees. lighted's input in the previous post is also invalid.

lighted · Post by **lighted** » Wed Sep 10, 2014 2:41 pm

Invalid input

Code: Select all

8
1 5
1 8
1 5
1 5
3 3 4 1 <- node 6 is missing here
2 8 5
1 8
3 7 6 2

I edited input in my previous post. Outputs are still the same

Farsan · Post by **Farsan** » Thu Sep 11, 2014 9:22 am

Thanks brianfry713,you always help

.Struggled to find out worse roots but at last ACED.

ebb · Post by **ebb** » Sat Jun 10, 2017 11:37 pm

Hi everyone,

I'm having trouble with this problem. My code (Java) passes all the inputs in this thread and in uDebug, but gets Runtime Error in the judge. I'm pretty sure it is the code that reads the input, because when I wrap it in a try catch I get Wrong Answer. When I remove the actual algorithm instead, I keep getting RE. When catching the exception, it doesn't matter if I stop completely, simply go to the next test case or ignore the exception: I always get Wrong Answer.

Here's my code in case someone can give me a hint of what could be wrong. I've removed the algorithm so we can focus on the input-reading code.

Edit: I removed the code, as I found my mistake.

UVa OJ Board

10459 - The Tree Root

Re: 10459 - The Tree Root

Re: 10459 - The Tree Root

Re: 10459 - The Tree Root

Re: 10459 - The Tree Root

Re: 10459 - The Tree Root

Re: 10459 - The Tree Root

Re: 10459 - The Tree Root

Re: 10459 - The Tree Root

Re: 10459 - The Tree Root

Re: 10459 - The Tree Root

Re: 10459 - The Tree Root

Re: 10459 - The Tree Root

Re: 10459 - The Tree Root

Re: 10459 - The Tree Root

Re: 10459 - The Tree Root