238. 银河英雄传说

Powered by:NEFU AB-IN

Link

238. 银河英雄传说

• 题意

  有一个划分为 N列的星际战场，各列依次编号为 1,2,…,N
  有 N艘战舰，也依次编号为 1,2,…,N，其中第 i号战舰处于第 i列。
  有 T条指令，每条指令格式为以下两种之一：
  M i j，表示让第 i号战舰所在列的全部战舰保持原有顺序，接在第 j号战舰所在列的尾部。
  C i j，表示询问第 i号战舰与第 j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。
  现在需要你编写一个程序，处理一系列的指令。

• 思路

  并查集——边带权的例题
  B站讲解录像！

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2023-02-20 21:51:02
  * @FilePath: \Acwing\238\238.cpp
  * @LastEditTime: 2023-02-21 11:27:22
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #undef int#define SZ(X) ((int)(X).size())
  #define ALL(X) (X).begin(), (X).end()
  #define IOS                                                                                                            \ios::sync_with_stdio(false);                                                                                       \cin.tie(nullptr);                                                                                                  \cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;const int N = 1e5 + 10, INF = 0x3f3f3f3f;int fa[N], d[N], sz[N];int find(int x)
  {if (fa[x] != x){int rt = find(fa[x]);d[x] += d[fa[x]];fa[x] = rt;}return fa[x];
  }signed main()
  {IOS;int t;cin >> t;for (int i = 1; i < N; ++i){fa[i] = i;sz[i] = 1;}while (t--){char q;int a, b;cin >> q >> a >> b;int ra = find(a), rb = find(b);if (q == 'M'){if (ra != rb){fa[ra] = rb;d[ra] = sz[rb];sz[rb] += sz[ra];}}else{if (ra != rb)cout << "-1\n";elsecout << max(0, abs(d[a] - d[b]) - 1) << '\n';}}return 0;
  }