Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

静态树通过,申请节点内存时,申请5000单位数组才通过,附代码

Posted by dut200901102 at 2010-12-22 00:15:09 on Problem 2003
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

const int MAXN=1010;
//2003

struct node
{
    int son[MAXN];
    int len;
    int id;
    int parent;
} p[MAXN*5];

char name[MAXN][25];

void print(int x,int dep)
{
    for(int i=0; i<dep; ++i)
        printf("+");
    printf("%s\n",name[x]);
    for(int i=0; i<p[x].len; ++i)
    {
        print(p[x].son[i],dep+1);
    }
}

void del(int x)
{
    if(p[x].len!=0)
        del(p[x].son[0]);
    int px=p[x].parent;
    for(int i=1; i<p[px].len; ++i)
    {
        p[p[px].son[i]].parent=x;
        p[p[px].son[i]].id=p[x].len;
        p[x].son[p[x].len++]=p[px].son[i];
    }
    p[px].len=1;
}

int main()
{
//    freopen("in.txt","r",stdin);
    int size=1,tem,root;
    char str[25];
    scanf("%s",name[0]);
    p[0].parent=-1;
    p[0].id=-1;
    p[0].len=0;
    root=0;
    while(scanf("%s",str)!=EOF)
    {
        if(strcmp(str,"print")==0)
        {
            print(root,0);
            printf("------------------------------------------------------------\n");
        }
        else if(strcmp(str,"fire")==0)
        {
            scanf("%s",str);
            for(int i=0; i<size; ++i)
            {
                if(strcmp(name[i],str)==0)
                {
                    tem=i;
                    break;
                }
            }
            if(tem==root)
            {
                if(p[root].len>0)
                {
                    del(p[tem].son[0]);
                    p[p[tem].son[0]].parent=p[tem].parent;
                    root=p[tem].son[0];
                }
            }
            else
            {
                if(p[tem].len==0)
                {
                    int px=p[tem].parent;
                    for(int i=p[tem].id; i<p[px].len-1; ++i)
                    {
                        p[p[px].son[i+1]].id--;
                        p[px].son[i]=p[px].son[i+1];
                    }
                    p[px].len--;
                }
                else
                {
                    del(p[tem].son[0]);
                    p[p[tem].son[0]].parent=p[tem].parent;
                    p[p[tem].son[0]].id=p[tem].id;
                    p[p[tem].parent].son[p[tem].id]=p[tem].son[0];
                }
            }
        }
        else
        {
            for(int i=0; i<size; ++i)
            {
                if(strcmp(str,name[i])==0)
                {
                    tem=i;
                    break;
                }
            }
            scanf("%s",str);
            scanf("%s",name[size]);
            p[tem].son[p[tem].len++]=size;
            p[size].len=0;
            p[size].id=p[tem].len-1;
            p[size++].parent=tem;
        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator