[ABC279] F - BOX

[Q] https://atcoder.jp/contests/abc279/tasks/abc279_f

60分かけても解けず。
UnionFindするんだけど、頂点をボールにするか箱にするか。またrootをボールにするか箱にするか。で永遠に混乱して抜けない。

結果
1. 頂点はボール。
2. rootはボールの代表。
3. 箱は、2.のボール代表(root) と箱をつなげる配列
boxToRoot[box] = root
rootToBox[root] = box
を用意すればよかった。

・考察
1. 1回集合したボールは離れたりしない。どんどん加算されるだけ。
2. なので、ボールはUnionFindで、Unite操作をしていい。
3. ボールと箱とを常にリアルタイムで全部更新するのは絶対TLE。
4. ボールのroot()を、ボールの代表値とみなせば、箱とボールを結びつける更新は1回でよい。

・実装

// root = ボールの集合の、代表番号
// unionfind = ボールの構造
// uniteするのはroot同士
 
// boxToRoot[box] = root
// rootToBox[root] = box
 
int main() {
  cincout();
 
  ll N, Q;
  cin >> N >> Q;
  UnionFind tree(N+Q+10);
  vector<ll> btr(N), rtb(N+Q+10);
  rep(i, N){
    btr[i] = i;
    rtb[i] = i;
  }
 
  ll mx = N;
  rep(i, Q) {
    ll op, x;
    cin >> op >> x;
    --x;
    if (op == 1){
      ll y;
      cin >> y;
      --y;
      if (btr[y] == -1) continue;
      if (btr[x] == -1){
        btr[x] = btr[y];
        rtb[btr[x]] = x;
        btr[y] = -1;
      }
      else{
        // yのボール集合をuniteする
        tree.unite(btr[x], btr[y]);
        ll rx = tree.root(btr[x]);
        btr[x] = rx;
        rtb[rx] = x;
        btr[y] = -1;
        // rtb[もとのry]は知らん
      }
    }
    else if (op == 2){
      if (btr[x] == -1){
        btr[x] = mx;
        rtb[mx] = x;
      }
      else{
        tree.unite(btr[x], mx);
      }
      ++mx;
    }
    else{
      cout << (rtb[tree.root(x)] + 1) << endl;
    }
  }
}

https://atcoder.jp/contests/abc279/submissions/36885163