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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

动态树 Memory Limit Exceeded ?? 包内存?? 求高人解答

Posted by shuaige123 at 2012-06-04 14:03:36 on Problem 1330
#include<cstdio>
#include<iostream>
using namespace std;
#define maxn 10100
struct edge_node{int next,y;}edge[maxn];
struct tree_node{int lc,rc,fa;
                #define lc(x) tr[x].lc
                #define rc(x) tr[x].rc
                #define fa(x) tr[x].fa
                }tr[maxn];
int first[maxn],ru[maxn],len,t,n,m;
inline void ins(int x,int y){
    len++;
    edge[len].y=y; edge[len].next=first[x]; first[x]=len;
    return;
}
inline void dfs(int x,int last){
    int k=first[x],y;
    while (k!=-1){
        y=edge[k].y;
        if (y!=last){
            fa(y)=x; lc(y)=rc(y)=0; 
            dfs(y,x);    
        }
        k=edge[k].next;    
    }
    return;
}
inline bool isroot(int x){return lc(fa(x))!=x && rc(fa(x))!=x;}
inline void l_rotate(int x){
    int y,z; y=fa(x); z=fa(y);
    if (lc(z)==y) lc(z)=x; if (rc(z)==y) rc(z)=x; fa(x)=z;
    fa(lc(x))=y; rc(y)=lc(x); lc(x)=y; fa(y)=x;
    return;
}
inline void r_rotate(int x){
    int y,z; y=fa(x); z=fa(y);
    if (lc(z)==y) lc(z)=x; if (rc(z)==y) rc(z)=x; fa(x)=z;
    fa(rc(x))=y; lc(y)=rc(x); rc(x)=y; fa(y)=x;
    return;
}
inline void splay(int x){
    int y,z;
    while (!isroot(x)){
        y=fa(x); z=fa(y);
        if (isroot(y)){
            if (lc(y)==x) r_rotate(x);
            else l_rotate(x);    
        }else{
            if (lc(z)==y){
                if (lc(y)==x) r_rotate(y),r_rotate(x);
                else l_rotate(x),r_rotate(x);    
            }else{
                if (lc(y)==x) r_rotate(x),l_rotate(x);
                else l_rotate(y),l_rotate(x);    
            }
        }
    }
    return;
}
inline void expose(int x){
    int y=0;
    while (x){
        splay(x); 
        rc(x)=y; y=x; x=fa(x);   
    }
    return;    
}
inline int lca(int x,int y){
    expose(y);
    y=0;
    while (x){
        splay(x);
        if (!fa(x)) return x;
        rc(x)=y; y=x; x=fa(x);   
    }
}
int main(){
    freopen("poj1330.in","r",stdin); freopen("poj1330.out","w",stdout);
    int i,x,y;
    scanf("%d",&t);
    while (t--){
        scanf("%d",&n); 
        memset(first+1,255,n*sizeof(int)); memset(ru+1,0,n*sizeof(int)); len=0;
        for (i=1; i<n; i++){
            scanf("%d%d",&x,&y); ru[y]++;
            ins(x,y); ins(y,x);    
        }
        for (i=1; i<=n; i++)
            if (ru[i]==0){
                fa(i)=lc(i)=rc(i)=0;
                dfs(i,0);
                break;
            }
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    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