uva 699

gistfile1.cpp

#include<iostream>
#include<cstring>
#include<string>
#include<stdio.h> 
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
bool used[1000000];
int a[1000000];
int n;
map<int,int>m;
struct node
  {
  node*left,*right;
  int v,h;
  node(int c)
    {
 left=right=NULL;
 v=c;
 }
  };
node*build(int k,int hh) 
{
used[k]=1;
node*root=new node(a[k]);
root->h=hh;
//if(a[k+1]==-1&&a[k+2]==-1){used[k+1]=used[k+2]=1;root->left=root->right=NULL;root->h=hh;return root;}
int i,j;
for(i=k+1;;i++)if(used[i]==0)break;
if(a[i]==-1){used[i]=1;root->left=NULL;}
else root->left=build(i,hh-1);
for(j=i+1;;j++)if(used[j]==0)break;
if(a[j]==-1){used[j]=1;root->right=NULL;} 
else root->right=build(j,hh+1);
return root;
}
void search(node*root)
{
if(root==NULL)return ;
int p=root->h,vv=root->v;
if(m.count(p)==0)m[p]=vv;
else m[p]=m[p]+vv;
search(root->left);
search(root->right);
}
int main()
{
int ca=0;
while(scanf("%d",&a[0])&&a[0]!=-1)
  {
  n=1;
  ca++;
  int k1=1,k2=0;
  while(scanf("%d",&a[n])==1)
    {
 if(a[n]==-1)k2++;
 else k1++;
    n++;
 if(k2==k1+1)break;
 }
  a[n]=0;
  memset(used,0,sizeof(used)); 
  m.clear();
  node*root=build(0,0);
  search(root);
  map<int,int>::iterator it=m.begin();
 cout<<"Case "<<ca<<":"<<endl;

  printf("%d",it->second);
  it++;
   // cout<<"sffsdfs1"<<endl;
  for(;it!=m.end();it++)
  {
   printf(" %d",it->second);
  }
  //cout<<"sffsdfs"<<endl;
  cout<<endl<<endl;;
  }


}