結果

問題 No.2290 UnUnion Find
ユーザー laoidnlaoidn
提出日時 2023-05-06 01:21:28
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 10,704 bytes
コンパイル時間 5,076 ms
コンパイル使用メモリ 249,380 KB
実行使用メモリ 26,112 KB
最終ジャッジ日時 2024-05-02 19:49:48
合計ジャッジ時間 23,947 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 355 ms
14,208 KB
testcase_03 AC 285 ms
19,968 KB
testcase_04 AC 288 ms
19,584 KB
testcase_05 AC 292 ms
19,584 KB
testcase_06 AC 288 ms
19,712 KB
testcase_07 AC 381 ms
19,584 KB
testcase_08 AC 289 ms
19,584 KB
testcase_09 AC 328 ms
19,584 KB
testcase_10 AC 294 ms
19,584 KB
testcase_11 AC 287 ms
19,584 KB
testcase_12 AC 292 ms
19,584 KB
testcase_13 AC 290 ms
19,584 KB
testcase_14 AC 290 ms
19,584 KB
testcase_15 AC 289 ms
19,584 KB
testcase_16 AC 289 ms
19,584 KB
testcase_17 AC 286 ms
19,712 KB
testcase_18 AC 293 ms
19,584 KB
testcase_19 AC 310 ms
20,608 KB
testcase_20 AC 335 ms
26,112 KB
testcase_21 WA -
testcase_22 AC 335 ms
16,896 KB
testcase_23 AC 332 ms
16,896 KB
testcase_24 AC 310 ms
22,784 KB
testcase_25 AC 344 ms
16,128 KB
testcase_26 AC 320 ms
24,448 KB
testcase_27 AC 319 ms
23,296 KB
testcase_28 AC 316 ms
18,688 KB
testcase_29 AC 309 ms
22,144 KB
testcase_30 WA -
testcase_31 AC 308 ms
21,248 KB
testcase_32 AC 343 ms
16,256 KB
testcase_33 AC 316 ms
18,688 KB
testcase_34 AC 323 ms
26,112 KB
testcase_35 AC 323 ms
24,192 KB
testcase_36 AC 339 ms
16,512 KB
testcase_37 AC 320 ms
18,048 KB
testcase_38 AC 338 ms
16,512 KB
testcase_39 AC 330 ms
17,152 KB
testcase_40 AC 316 ms
23,808 KB
testcase_41 AC 347 ms
16,000 KB
testcase_42 AC 308 ms
20,224 KB
testcase_43 AC 307 ms
19,968 KB
testcase_44 AC 287 ms
19,712 KB
testcase_45 WA -
testcase_46 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
#include <iostream>
#include <vector>
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<int>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using pii = pair<long long, long long>;
using mint = modint1000000007;
const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) begin(n), end(n)
#define fore(i, a) for (auto &i : a)
#define IN(a, x, b) (a <= x && x < b)
#define IN(a, x, b) (a <= x && x < b)
#define INIT                        \
  std::ios::sync_with_stdio(false); \
  std::cin.tie(0);
template <class T>
inline T CHMAX(T &a, const T b) {
  return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T &a, const T b) {
  return a = (a > b) ? b : a;
}
#include <algorithm>  // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>     // bitset
#include <cctype>     // isupper, islower, isdigit, toupper, tolower
#include <cstdint>    // int64_t, int*_t
#include <cstdio>     // printf
#include <deque>      // deque
#include <iostream>   // cout, endl, cin
#include <map>        // map
#include <queue>      // queue, priority_queue
#include <set>        // set
#include <stack>      // stack
#include <string>     // string, to_string, stoi
#include <tuple>      // tuple, make_tuple
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <utility>        // pair, make_pair
#include <vector>         // vector
using namespace std;
ll GCD(ll m, ll n) {
  // ベースケース
  if (n == 0) return m;

  // 再帰呼び出し
  return GCD(n, m % n);
}

ll minlong = 0;

long long Power(long long a, long long b, long long m) {
  long long p = a, Answer = 1;
  for (int i = 0; i < 63; i++) {
    ll wari = (1LL << i);
    if ((b / wari) % 2 == 1) {
      Answer = (Answer * p) % m;  // 「a の 2^i 乗」が掛けられるとき
    }
    p = (p * p) % m;
  }
  return Answer;
}

// a ÷ b を m で割った余りを返す関数
long long Division(long long a, long long b, long long m) {
  return (a * Power(b, m - 2, m)) % m;
}

// nCr mod 1000000007 を返す関数
long long nCk(ll n, ll r) {
  const long long M = 1000000007;

  // 手順 1: 分子 a を求める
  long long a = 1;
  for (int i = 1; i <= n; i++) a = (a * i) % M;

  // 手順 2: 分母 b を求める
  long long b = 1;
  for (int i = 1; i <= r; i++) b = (b * i) % M;
  for (int i = 1; i <= n - r; i++) b = (b * i) % M;

  // 手順 3: 答えを求める
  return Division(a, b, M);
}
using Interval = pair<ll, ll>;
// nCk mint を返す関数。
ll modnCk(ll n, ll r) {
  ll a = 1;
  for (ll i = n; i > n - r; i--) {
    a *= i;
    a /= n + 1 - i;
  }
  return a;
}
// 終点時間でsortをかけるのに必要(区間スケジューリング問題など)
bool cmp(const Interval &a, const Interval &b) { return a.second < b.second; }
vll dycstra(vector<vector<pair<ll, ll>>> G, ll N, ll K) {
  vb kaku(N, false);
  vll cur(N, INF);
  cur[K] = 0;
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> Q;
  Q.push(make_pair(cur[K], K));
  while (!Q.empty()) {
    ll pos = Q.top().second;
    Q.pop();
    if (kaku[pos]) continue;
    kaku[pos] = true;
    for (ll i = 0; i < G[pos].size(); i++) {
      ll nex = G[pos][i].first;
      ll cost = G[pos][i].second;
      if (cur[nex] > cur[pos] + cost) {
        cur[nex] = cur[pos] + cost;
        Q.push(make_pair(cur[nex], nex));
      }
    }
  }
  return cur;
}
ll f(ll x, vll &memo, ll D, vector<pair<ll, ll>> &X) {
  if (memo[x] != -1) return memo[x];
  if (x < D) return 0;
  ll y = x - D;
  ll x1, x2, y1, y2;
  tie(x1, y1) = X[y];
  tie(x2, y2) = X[x];
  ll cost = abs(x1 - x2) + abs(y1 - y2);
  ll res = cost + f(y, memo, D, X);
  return memo[x] = res;
}
template <class T>
struct BIT {
  int n;                  // 要素数
  vector<T> bit[600000];  // データの格納先
  BIT(int n_) { init(n_); }
  void init(int n_) {
    n = n_ + 1;
    for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
  }
  void add_sub(int p, int i, T x) {
    for (int idx = i; idx < n; idx += (idx & -idx)) {
      bit[p][idx] += x;
    }
  }
  void add(int l, int r, T x) {  // [l,r) の区間で加算
    add_sub(0, l, -x * (l - 1));
    add_sub(0, r, x * (r - 1));
    add_sub(1, l, x);
    add_sub(1, r, -x);
  }
  T sum_sub(int p, int i) {
    T s(0);
    for (int idx = i; idx > 0; idx -= (idx & -idx)) {
      s += bit[p][idx];
    }
    return s;
  }
  T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i; }
  // sum'(i)=sum(i)-x(l-i)+xi(sum'(i)は加算後の合計値sum(i)測酸前の合計値)
  T query(int l, int r) { return sum(r - 1) - sum(l - 1); }
  // 任意の区間を計算することが可能これは[l,r)の区間和を計算している。
  int lower_bound(T w) {  // a_1 + a_2 + ... + a_x >= w となるような最小の x
                          // を求める(ただし a_i >= 0)
    if (w <= 0) {
      return 0;
    } else {
      int x = 0, r = 1;
      while (r < n) r = r << 1;
      for (int len = r; len > 0;
           len = len >> 1) {  // 長さlenは1段下るごとに半分に
        if (x + len < n && bit[x + len] < w) {  // 採用するとき
          w -= bit[x + len];
          x += len;
        }
      }
      return x + 1;
    }
  }
};
vll BFS(vvll &G, ll &x) {
  vll cut(G.size(), INF);
  queue<ll> Q;
  Q.push(x);
  cut[x] = 0;
  while (!Q.empty()) {
    ll a = Q.front();
    Q.pop();
    rep(i, G[a].size()) {
      if (cut[G[a][i]] > cut[a] + 1) {
        cut[G[a][i]] = cut[a] + 1;
        Q.push(G[a][i]);
      }
    }
  }
  return cut;
}
template <class Abel>
struct UnionFind {
  vector<int> par;
  vector<int> rank;
  vector<Abel> diff_weight;
  vector<int> siz;
  UnionFind(int n = 1, Abel SUM_UNITY = 0) { init(n, SUM_UNITY); }

  void init(int n = 1, Abel SUM_UNITY = 0) {
    par.resize(n);
    rank.resize(n);
    diff_weight.resize(n);
    siz.resize(n);
    for (int i = 0; i < n; ++i)
      par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY, siz[i] = 1;
  }

  int root(int x) {
    if (par[x] == x) {
      return x;
    } else {
      int r = root(par[x]);
      diff_weight[x] +=
          diff_weight[par[x]];  // 累積和をとることで重みがつけられる。
      return par[x] = r;
    }
  }

  Abel weight(int x) {
    root(x);                // 経路圧縮
    return diff_weight[x];  // 重みを返す
  }

  bool issame(int x, int y) {
    return root(x) == root(y);  // 通常時も同じ
  }

  // weight(y) - weight(x) = w となるように merge する
  bool merge(int x, int y, Abel w) {
    // x と y それぞれについて、 root との重み差分を補正
    w += weight(x);
    w -= weight(y);
    // x と y の root へ (x と y が既につながっていたら false を返すようにした)
    x = root(x);
    y = root(y);
    if (x == y) return false;

    // rank[x] >= rank[y] となるように x と y を swap (それに合わせて w
    // も符号反転します)これはUnion by
    // rankと呼ばれ根の高さをO(logN)で抑えられる手法である。
    if (rank[x] < rank[y]) swap(x, y), w = -w;

    // y (のroot) を x (のroot)
    // の下にくっつける(高さが低い方の根付き木を高いほうに併合する)
    if (rank[x] == rank[y]) ++rank[x];
    siz[x] += siz[y];
    par[y] = x;

    // x が y の親になるので、x と y の差分を diff_weight[y] に記録
    diff_weight[y] = w;
    return true;
  }
  Abel diff(int x, int y) { return weight(y) - weight(x); }
  int size(int x) { return siz[root(x)]; }
};

void Yes(bool b) {
  if (b)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}
vector<long long> yaku(long long n) {
  vector<long long> ret;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  sort(ret.begin(), ret.end());  // 昇順に並べる
  return ret;
}
// #include <atcoder/lazysegtree>用
using S = long long;
using F = long long;

S op(S a, S b) { return std::max(a, b); }
S e() { return -INF; }
S mapping(F f, S x) { return f + x; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> Q;
ll N, M, K, XP = 0;
vll cur;
vll A;
void dfs(ll now, ll past, vvll G) {
  A[now] = true;
  rep(i, G[now].size()) {
    if (G[now][i] != past && !A[G[now][i]]) {
      dfs(G[now][i], now, G);
    }
  }
  cur[now] = XP;
  XP++;
}
int GetRandom(int min, int max) {
  return min + (rand() * (max - min) / (RAND_MAX));
}

int main() {
  cout << fixed << setprecision(20);
  ll N, M, K, L, ans = 0, count;
  cin >> N >> M;
  ll memo = -1;
  dsu d(N);
  vvll G(M);
  vll P;
  rep(i, M) {
    ll a, b, c;
    cin >> a >> b;
    if (a == 1) {
      cin >> c;
      --b, --c;
      G[i].push_back(a);
      G[i].push_back(b);
      G[i].push_back(c);
      d.merge(b, c);

    } else {
      --b;
      G[i].push_back(a);
      G[i].push_back(b);
    }
    if (d.size(0) == N) memo = i;
  }
  if (memo == -1) {
    auto X = d.groups();
    ll a1, b1, c1, d1;
    a1 = X[0][0];
    b1 = d.leader(a1);
    c1 = X[1][0];
    d1 = d.leader(c1);
    rep(i, M) {
      if (G[i][0] == 2) {
        if (d.leader(G[i][1]) == b1) {
          cout << d1+1 << endl;
        } else
          cout << b1+1 << endl;
      }
    }
    return 0;
  }
  dsu d2(N);
  //cout << memo << endl;
  rep(i, memo-1) {
    if (G[i][0] == 1) {
      d2.merge(G[i][1], G[i][2]);
    }
  }

  ll han = 0;
  auto X = d2.groups();
    //cout << X.size() << endl;
  if (X.size() == 1) {
    rep(i, M) {
      if (G[i][0] == 2) cout << -1 << endl;
    }
    return 0;
  }
  ll a1, b1, c1, d1;
  a1 = X[0][0];
  b1 = d2.leader(a1);
  c1 = X[1][0];
  d1 = d2.leader(c1);

  rep(i, M) {
    if (G[i][0] == 2) {
      if (i >= memo) {
        cout << -1 << endl;
        continue;
      }
      if (d2.leader(G[i][1]) == b1) {
        cout << d1+1 << endl;
      } else
        cout << b1+1 << endl;
    }
  }
  return 0;
}
0