萌新并查集WA22pts求助
查看原帖
萌新并查集WA22pts求助
529247
BLX32M_10楼主2024/12/12 16:25
#include <bits/stdc++.h>
#define int long long
using namespace std;
int fa[30005], val[30005], sz[30005], add[30005];
int ad = 0;
inline int find(int x)
{
    ad += add[fa[x]];
    return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
inline int fd(int x)
{
    ad = 0;
    int res = find(x);
    val[x] += ad;
    add[x] += ad;
    return res;
}
inline void mg(int x, int y)
{
    x = fd(x);
    y = fd(y);
    add[y] += sz[x];
    val[y] += add[y];
    sz[x] += sz[y];
    fa[y] = x;
}
inline void prt()
{
    for (int i = 1; i <= 5; i++)
    {
        printf("%lld:\n", i);
        printf("fa:%lld val:%lld sz:%lld, add:%lld\n", fa[i], val[i], sz[i], add[i]);
    }
}
signed main()
{
    int _;
    scanf("%lld", &_);
    for (int i = 1; i <= 30000; i++)
        fa[i] = i, val[i] = sz[i] = 1;
    while (_--)
    {
        char op;
        int x, y;
        scanf("\n%c %lld %lld", &op, &x, &y);
        if (op == 'M')
        {
            mg(y, x);
        }
        else
        {
            if (fd(x) != fd(y))
                puts("-1");
            else
                printf("%lld\n", abs(val[x] - val[y]) - 1);
        }
        // prt();
    }
    return 0;
}
2024/12/12 16:25
加载中...