結果

問題 No.2290 UnUnion Find
コンテスト
ユーザー a01sa01to
提出日時 2024-02-13 00:27:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 423 ms / 2,000 ms
コード長 999 bytes
コンパイル時間 2,270 ms
コンパイル使用メモリ 206,424 KB
最終ジャッジ日時 2025-02-19 05:48:45
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
  #include "settings/debug.cpp"
  #define _GLIBCXX_DEBUG
#else
  #define Debug(...) void(0)
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

#include<atcoder/dsu>

int main() {
  int n,q;cin>>n>>q;
  atcoder::dsu d(n);
  set<int> leaders;
  rep(i, n) leaders.insert(i);
  while(q--) {
    int t;cin>>t;
    if (t==1) {
      int u,v;cin>>u>>v;
      --u,--v;
      int lu = d.leader(u);
      int lv = d.leader(v);
      d.merge(u, v);
      int luv = d.leader(u);
      if (luv != lu) leaders.erase(lu);
      if (luv != lv) leaders.erase(lv);
    }else{
      int v;cin>>v;
      --v;
      if (leaders.size() == 1) {
        cout << -1 << endl;
      }
      else {
        if (*leaders.begin() != d.leader(v)) {
          cout << *leaders.begin() + 1 << endl;
        }
        else {
          cout << *leaders.rbegin() + 1 << endl;
        }
      }
    }
  }
  return 0;
}
0