Elven Postman 두 갈래 나무 만들기

4145 단어
    //  ,   ,  
    // , 
    //  ,  'E' ,  'W'
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    using namespace std ;
    const int maxn = 1010 ;
    char ans[maxn][maxn] ;
    char a[maxn] ;
    int len[maxn] ;
    int edge[maxn][2] ;
    void dfs(int u , int pre , int num , int step)
    {
        if(!pre)
          a[step] = 'E' ;
        else
          a[step] = 'W' ;
        if(!edge[u][pre])
        {
            edge[u][pre] = num ;
            memcpy(ans[num] , a , sizeof(a)) ;
            len[num] = step ;
            return  ;
        }
        if(edge[u][pre] > num)
            dfs(edge[u][pre] , 0 , num , step+1) ;
        else
            dfs(edge[u][pre] , 1 , num , step+1) ;
    }
    int main()
    {
       // freopen("in.txt" , "r" , stdin) ;
        int t ;
        scanf("%d" , &t) ;
        while(t--)
        {
            int n;
            scanf("%d" , &n) ;
            memset(edge , 0 , sizeof(edge)) ;
            int tmp ;
            int root ;
            scanf("%d" , &root);
            len[root] = -1 ;
            for(int i = 2;i <= n;i++)
            {
                scanf("%d" , &tmp) ;
                dfs(root , tmp > root , tmp , 0) ;
            }
            int q ;
            scanf("%d" , &q) ;
            while(q--)
            {
                scanf("%d" , &tmp) ;
                for(int i = 0 ;i <= len[tmp];i++)
                printf("%c" , ans[tmp][i]) ;
                puts("") ;
            }
        }
    }




좋은 웹페이지 즐겨찾기