ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1069. Prufer Code

foxX help me please [8] // Problem 1069. Prufer Code 12 Apr 2003 19:30
i just can't understand what does this problem want from me.
1. what is the number of a vertex? (is it by any chance the cost of the way connecting its two extremes?)
2. what is the rule by which different lines in the graph are assigned costs?
in the example:
   1
  /  4   6
     |
     2
    /    3   5

what are the costs of
(1,4)
(1,6)
(6,2)
(2,3)
(2,5)
?

thank you
        foxx@email.ro
TheBlaNK Re: help me please [7] // Problem 1069. Prufer Code 13 Apr 2003 00:40
the problem is
u are given a prufer code
and u must output what graph that give this code

ie in the sample input

4-1-6-2-5
         |
         3

to construct the prufer code is look all leaf and find the smallest
then next code=the number of vertex that connect it

we find that
leaf = 4 3 5 ( 3 is the smallest then write 2 down )

then the graph will be
4-1-6-2-5

code = 2

leaf = 4 5 ( 4 is the smallest the write 1 down )

then the graph will be
1-6-2-5

code = 2 1

leaf= 1 5 ( 1 is the smallest then write 6 down )
graph
6-2-5

code= 2 1 6

and so on..
foxX thank you very much, i've got AC :) ~nt~ [6] // Problem 1069. Prufer Code 13 Apr 2003 23:14
> the problem is
> u are given a prufer code
> and u must output what graph that give this code
>
> ie in the sample input
>
> 4-1-6-2-5
>          |
>          3
>
> to construct the prufer code is look all leaf and find the smallest
> then next code=the number of vertex that connect it
>
> we find that
> leaf = 4 3 5 ( 3 is the smallest then write 2 down )
>
> then the graph will be
> 4-1-6-2-5
>
> code = 2
>
> leaf = 4 5 ( 4 is the smallest the write 1 down )
>
> then the graph will be
> 1-6-2-5
>
> code = 2 1
>
> leaf= 1 5 ( 1 is the smallest then write 6 down )
> graph
> 6-2-5
>
> code= 2 1 6
>
> and so on..
>
TheBlaNK Re: thank you very much, i've got AC :) ~nt~ [5] // Problem 1069. Prufer Code 14 Apr 2003 00:07
wow that's sound great : )

but mine's still got TL - -'
i don't know why(i already use heap)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 30000
#define CON 2000000000
struct node { long info; struct node *next; };
typedef struct node *nodeptr;
long arr[MAX*2],num[MAX],deg[MAX],n;
long nheap;
FILE *fp,*fx;
nodeptr res[MAX];
void input(void)
{
 long tmp;
 n=1;
 while(fscanf(fp,"%ld",&tmp)!=EOF)
   {
    num[n++]=tmp;
    deg[tmp]++;
   }
}
nodeptr getnode(long i,nodeptr next)
{
 nodeptr p;
  p=(nodeptr)malloc(sizeof(struct node));
  p->next=next; p->info=i;
 return p;
}
void add(long a,long b)
{
 nodeptr p,q;
 if( res[a]==NULL||b<res[a]->info)
  { res[a]=getnode(b,res[a]); return; }
 for(p=q=res[a];p!=NULL&&b>p->info;p=p->next) q=p;
 p=getnode(b,p); q->next=p;
}
void del(void)
{
 long pos,tmp,nextpos;
 arr[1]=CON;
 for(pos=1,tmp=arr[1];;)
  {
   if(arr[pos*2]<arr[pos*2+1]) nextpos=pos*2;
   else nextpos=pos*2+1;
   if(tmp>arr[nextpos])
     { arr[pos]=arr[nextpos]; pos=nextpos; }
   else break;
  }
 arr[pos]=tmp;
}
void insert(long a)
{
 long pos,k;
 for(k=10000;;k--) if(arr[k]==CON) break;
 nheap++;
 arr[k]=a;
 for(pos=k;pos>1;pos/=2)
  {
   if(a<arr[pos/2]) arr[pos]=arr[pos/2];
   else break;
  }
 arr[pos]=a;
}
void process(void)
{
 long i;
 for(i=0;i<MAX*2;i++) arr[i]=CON;
 for(i=1,nheap=0;i<=n;i++) if(!deg[i]) arr[++nheap]=i;
 for(i=1;i<n;i++)
   {
     add(arr[1],num[i]); add(num[i],arr[1]);
     del();
     deg[num[i]]--; if(!deg[num[i]]) insert(num[i]);
   }
}
void output(void)
{
 long i;
 nodeptr p;
 for(i=1;i<=n;i++)
  {
   fprintf(fx,"%ld:",i);
   for(p=res[i];p!=NULL;p=p->next) fprintf(fx," %ld",p->info);
   fprintf(fx,"\n");
  }
}
int main()
{
  fp=stdin; fx=stdout;
// fp=fopen("1069.in","r"); fx=fopen("1069.out","w");
  input();
  process();
  output();
// fclose(fp); fclose(fx);
 return 0;
}
foxX hmm [4] // Problem 1069. Prufer Code 17 Apr 2003 03:09
i can't see why you dudes use heaps...
and i am too dumb at this time to understand your src
the algo goes like:
----------------------------------------------------
1: read i and inc number of apparitions of the node i;
2: last = 1;
3: for i = 1 .. n
4:   while apparitions of node[last] > 0 inc last;
   // now you have found (i, last) a valid vertex in the source tree
5:   memorize vertices (i, last) and (last, i);
6:   dec apparitions[i];
7:   dec apparitions[last];   // it gets -1 which is different of 0 :)
8:   if apparitions[i] = 0 and i < last
9:       last = i;
----------------------------------------------------

in 5 i simply push the 2 pairs in one stack and in final i take from each of n stacks the values and brutely qsort() on em.
got .3secs @ 600 kBs
foxx@email.ro
ahyangyi_newid thanx, i found the algo now :) [3] // Problem 1069. Prufer Code 23 Apr 2004 06:54
ahyangyi_newid wait, I think i'v 2 us heap, maybe i went wrong? [2] // Problem 1069. Prufer Code 23 Apr 2004 06:56
ahyangyi_newid In the worst case Your's will be O(n^2) & get TL [1] // Problem 1069. Prufer Code 23 Apr 2004 06:58
ahyangyi_newid hehe, 0.078sec without heap. // Problem 1069. Prufer Code 23 Apr 2004 07:12
I see. Such as Qsort is O(n^2) in the worst case, you algo is also fast for average cases...