洛谷P4312 [COCI 2009] OTOCI / 极地旅行社(link-cut-tree)

题目描述

不久之前，Mirko建立了一个旅行社，名叫“极地之梦”。这家旅行社在北极附近购买了N座冰岛，并且提供观光服务。

当地最受欢迎的当然是帝企鹅了，这些小家伙经常成群结队的游走在各个冰岛之间。Mirko的旅行社遭受一次重大打击，以至于观光游轮已经不划算了。旅行社将在冰岛之间建造大桥，并用观光巴士来运载游客。

Mirko希望开发一个电脑程序来管理这些大桥的建造过程，以免有不可预料的错误发生。这些冰岛从1到N标号。一开始时这些岛屿没有大桥连接，并且所有岛上的帝企鹅数量都是知道的。每座岛上的企鹅数量虽然会有所改变，但是始终在[0, 1000]之间。你的程序需要处理以下三种命令：

bridge A B：询问结点A与结点B是否连通。如果是则输出“no”。否则输出“yes”，并且在结点A和结点B之间连一条无向边。
penguins A X：将结点A对应的权值wA修改为X。
excursion A B：如果结点A和结点B不连通，则输出“impossible”。否则输出结点A到结点B的路径上的点对应的权值的和。

给出q个操作，要求在线处理所有操作。

输入输出格式

输入格式：

第一行包含一个整数n(1<=n<=30000)，表示节点的数目。

第二行包含n个整数，第i个整数表示第i个节点初始时对应的权值。

第三行包含一个整数q(1<=n<=300000)，表示操作的数目。

以下q行，每行包含一个操作，操作的类别见题目描述。

任意时刻每个节点对应的权值都是1到1000的整数。

输出格式：

输出所有bridge操作和excursion操作对应的输出，每个一行。

输入输出样例

输入样例#1：
复制

5

4 2 4 5 6

10

excursion 1 1

excursion 1 2

bridge 1 2

excursion 1 2

bridge 3 4

bridge 3 5

excursion 4 5

bridge 1 3

excursion 2 4

excursion 2 5

输出样例#1：复制

4

impossible

yes

6

yes

yes

15

yes

15

16

说明

数据范围：1<=n<=30000, 1<=q<=300000, 0<=wi<=1000。

题解：放学前二十分钟准备切道水题，结果因为多写了个puts身败名裂……

其他没什么好说的了，基本和洛谷那道模板一模一样

代码如下：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 30030

#define lson ch[x][0]

#define rson ch[x][1]

using namespace std;

int ch[N][],f[N],v[N],sum[N],tag[N];

int not_root(int now)

{

    register int x=f[now];

    return lson==now||rson==now;

}

int push_up(int x)

{

    sum[x]=sum[lson]+sum[rson]+v[x];

}

int rev(int x)

{

    swap(lson,rson);

    tag[x]^=;

}

int push_down(int x)

{

    if(tag[x])

    {

        rev(lson);

        rev(rson);

        tag[x]^=;

    }

}

int rotate(int x)

{

    int y=f[x],z=f[y],kd=ch[y][]==x,xs=ch[x][!kd];

    if(not_root(y)) ch[z][ch[z][]==y]=x;

    ch[x][!kd]=y;

    ch[y][kd]=xs;

    if(xs) f[xs]=y;

    f[y]=x;

    f[x]=z;

    push_up(y);

}

int push_all(int x)

{

    if(not_root(x)) push_all(f[x]);

    push_down(x);

}

int splay(int x)

{

    int y,z;

    push_all(x);

    while(not_root(x))

    {

        y=f[x],z=f[y];

        if(not_root(y)) (ch[y][]==x)^(ch[z][]==y)?rotate(x):rotate(y);

        rotate(x);

    }

    push_up(x);

}

int access(int x)

{

    for(int y=;x;y=x,x=f[x])

    {

        splay(x);

        rson=y;

        push_up(x);

    }

}

int make_root(int x)

{

    access(x);splay(x);

    rev(x);

}

int split(int x,int y)

{

    make_root(x);

    access(y);splay(y);

}

int find_root(int x)

{

    access(x);splay(x);

    while(lson)

    {

        push_down(x);

        x=lson;

    }

    return x;

}

int link(int x,int y)

{

    make_root(x);

    if(find_root(y)==x) return ;

    f[x]=y;

    return ;

}

int cut(int x,int y)

{

    make_root(x);

    if(find_root(y)!=x||f[x]!=y||rson) return ;

    f[x]=ch[y][]=;

    return ;

}

int n,m;

char op[];

int main()

{

    scanf("%d",&n);

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

    {

        scanf("%d",&v[i]);

    }

    scanf("%d",&m);

    int from,to;

    while(m--)

    {

        scanf("%s",op);

        puts("");

        if(op[]=='e')

        {

            scanf("%d%d",&from,&to);

            make_root(from);

            if(find_root(to)!=from)

            {

                puts("impossible");

                continue;

            }

            printf("%d\n",sum[to]);

        }

        if(op[]=='p')

        {

            scanf("%d%d",&from,&to);

            splay(from);

            v[from]=to;

        }

        if(op[]=='b')

        {

            scanf("%d%d",&from,&to);

            if(link(from,to)) puts("yes");

            else puts("no");

        }

    }

}

巴特西

洛谷P4312 [COCI 2009] OTOCI / 极地旅行社(link-cut-tree)

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章