[Usaco2004 Open]Cube Stacking 方块游戏

题面:

约翰和贝茜在玩一个方块游戏．编号为1到n的n(1≤n≤30000)个方块正放在地上．每个构成一个立方柱．

游戏开始后，约翰会给贝茜发出P(1≤P≤100000)个指令．指令有两种：

1．移动(M)：将包含X的立方柱移动到包含Y的立方柱上．

2．统计(C):统计名含X的立方柱中，在X下方的方块数目．

写个程序帮贝茜完成游戏．

解法：带权并查集，记录一个底面，顶面，x上面的立方体的个数。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int N=;

int n,dep[N],dis[N],fa[N];

int find(int x) {

    if(x!=fa[x]) {

        int fx=fa[x];

        fa[x]=find(fx);

        dep[x]=dep[fx];

        dis[x]+=dis[fx];

    }

    return fa[x];

}

inline void merge(int x,int y) {

    int fx=find(x),fy=find(y);

    fa[fy]=fx;dis[fy]=dis[dep[x]]+;dep[fx]=dep[fy];

    find(dep[fx]),find(dep[fy]);

}

int main() {

    scanf("%d",&n);

    for(int i=;i<N;i++) fa[i]=dep[i]=i;

    char opt[];int x,y;

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

        scanf("%s",opt);

        switch (opt[]) {

            case 'M' :scanf("%d%d",&x,&y);merge(x,y);break;

            case 'C' :scanf("%d",&x);find(x);printf("%d\n",dis[dep[x]]-dis[x]);break;

        }

    }

}

[Usaco2004 Open]Cube Stacking 方块游戏

巴特西

[Usaco2004 Open]Cube Stacking 方块游戏

最新文章

热门文章