AC日记——队列安排 洛谷 P1160

队列安排

思路：

　　链表裸题；

来，上代码：

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

#define maxn 100005

struct ListType {

    int pre,suc,key;

};

struct ListType list[maxn<<];

int tot=,n,m,sta=,End=,to[maxn];

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

int main()

{

    to[]=;

    list[sta].suc=;

    list[End].pre=;

    list[].key=;

    list[].pre=sta;

    list[].suc=End;

    in(n);int v,p;

    for(int i=;i<=n;i++)

    {

        in(v),in(p);

        to[i]=++tot;

        list[tot].key=i;

        int pos=to[v];

        if(p)

        {

            int cur=list[pos].suc;

            list[pos].suc=tot;

            list[tot].pre=pos;

            list[tot].suc=cur;

            list[cur].pre=tot;

        }

        else

        {

            int cur=list[pos].pre;

            list[pos].pre=tot;

            list[tot].suc=pos;

            list[tot].pre=cur;

            list[cur].suc=tot;

        }

    }

    in(m);

    while(m--)

    {

        in(v);

        if(to[v])

        {

            int pos=to[v];

            to[v]=;

            list[list[pos].pre].suc=list[pos].suc;

            list[list[pos].suc].pre=list[pos].pre;

        }

    }

    for(int now=list[sta].suc;now!=End;now=list[now].suc)

    {

        now!=list[End].pre?printf("%d ",list[now].key):printf("%d\n",list[now].key);

    }

    return ;

}