結果

問題 No.1054 Union add query
ユーザー SSRSSSRS
提出日時 2022-09-21 04:58:03
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 795 ms / 2,000 ms
コード長 3,257 bytes
コンパイル時間 1,897 ms
コンパイル使用メモリ 182,020 KB
実行使用メモリ 63,572 KB
最終ジャッジ日時 2023-08-23 19:53:20
合計ジャッジ時間 8,045 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 630 ms
22,492 KB
testcase_04 AC 787 ms
63,572 KB
testcase_05 AC 582 ms
15,352 KB
testcase_06 AC 627 ms
48,516 KB
testcase_07 AC 567 ms
47,404 KB
testcase_08 AC 519 ms
50,268 KB
testcase_09 AC 795 ms
60,644 KB
testcase_10 AC 301 ms
60,668 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
struct unionfind{
  vector<int> r, p;
  int t;
  unionfind(int N): r(N * 2 - 1, -1), p(N * 2 - 1, -1), t(N){
  }
  int root(int x){
    if (r[x] == -1){
      return x;
    } else {
      r[x] = root(r[x]);
      return r[x];
    }
  }
  bool same(int x, int y){
    return root(x) == root(y);
  }
  void unite(int x, int y){
    x = root(x);
    y = root(y);
    if (x != y){
      p[x] = t;
      p[y] = t;
      r[x] = t;
      r[y] = t;
      t++;
    }
  }
};
const int LOG = 17;
struct lowest_common_ancestor{
  vector<int> d;
  vector<vector<int>> pp;
  lowest_common_ancestor(vector<int> &p, vector<int> &d): d(d){
    int N = p.size();
    pp = vector<vector<int>>(LOG, vector<int>(N, -1));
    pp[0] = p;
    for (int i = 0; i < LOG - 1; i++){
      for (int j = 0; j < N; j++){
        if (pp[i][j] != -1){
          pp[i + 1][j] = pp[i][pp[i][j]];
        }
      }
    }
  }
  int la(int v, int k){
    for (int i = 0; i < LOG; i++){
      if ((k >> i & 1) == 1){
        v = pp[i][v];
      }
    }
    return v;
  }
  int lca(int u, int v){
    if (d[u] > d[v]){
      swap(u, v);
    }
    v = la(v, d[v] - d[u]);
    if (u == v){
      return u;
    }
    for (int i = LOG - 1; i >= 0; i--){
      if (pp[i][u] != pp[i][v]){
        u = pp[i][u];
        v = pp[i][v];
      }
    }
    return pp[0][v];
  }
};
void dfs(vector<vector<int>> &c, vector<int> &in, vector<int> &out, int &t, int v){
  in[v] = t;
  t++;
  for (int w : c[v]){
    dfs(c, in, out, t, w);
  }
  out[v] = t;
}
template <typename T>
struct dual_invertible_binary_indexed_tree{
  int N;
  vector<T> BIT;
  function<T(T, T)> f;
  function<T(T)> inv;
  T E;
  dual_invertible_binary_indexed_tree(int N, function<T(T, T)> f, function<T(T)> inv, T E): N(N), BIT(N + 1, E), f(f), inv(inv), E(E){
  }
  void add(int i, T x){
    while (i > 0){
      BIT[i] = f(BIT[i], x);
      i -= i & -i;
    }
  }
  void add(int l, int r, T x){
    add(l, inv(x));
    add(r, x);
  }
  T operator [](int i){
    i++;
    T ans = E;
    while (i <= N){
      ans = f(ans, BIT[i]);
      i += i & -i;
    }
    return ans;
  }
};
int main(){
  int N, Q;
  cin >> N >> Q;
  unionfind UF(N);
  vector<tuple<int, int, int>> query;
  for (int i = 0; i < Q; i++){
    int T, A, B;
    cin >> T >> A >> B;
    if (T == 1){
      A--;
      B--;
      UF.unite(A, B);
    }
    if (T == 2){
      A--;
      query.push_back(make_tuple(0, UF.root(A), B));
    }
    if (T == 3){
      A--;
      query.push_back(make_tuple(1, A, 0));
    }
  }
  vector<int> p = UF.p;
  p.push_back(-1);
  for (int i = 0; i < N * 2 - 1; i++){
    if (p[i] == -1){
      p[i] = N * 2 - 1;
    }
  }
  vector<vector<int>> c(N * 2);
  for (int i = 0; i < N * 2 - 1; i++){
    c[p[i]].push_back(i);
  }
  vector<int> in(N * 2), out(N * 2);
  int t = 0;
  dfs(c, in, out, t, N * 2 - 1);
  dual_invertible_binary_indexed_tree<int> BIT(N * 2, plus<int>(), negate<int>(), 0);
  int M = query.size();
  for (int i = 0; i < M; i++){
    if (get<0>(query[i]) == 0){
      int v = get<1>(query[i]);
      int x = get<2>(query[i]);
      BIT.add(in[v], out[v], x);
    }
    if (get<0>(query[i]) == 1){
      int v = get<1>(query[i]);
      cout << BIT[in[v]] << endl;
    }
  }
}
0