test/aoj/DSL/DSL_1_B.test.cpp

View this file on GitHub
Last update: 2023-11-11 17:58:53+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_B

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_B"

#include "../../../template/template.hpp"

#include "../../../graph/Weighted-UnionFind.hpp"

int main(){
  int n,q;
  cin >> n >> q;
  UnionFindW<int> tree(n);
  rep(i, q){
    int t; cin >> t;
    if(!t){
      int x,y,z;
      cin >> x >> y >> z;
      tree.merge(x, y, z);
    }else{
      int x,y;
      cin >> x >> y;
      if(!tree.same(x, y)) cout << "?\n";
      else cout << tree.diff(x, y) << "\n";
    }
  }
}

#line 1 "test/aoj/DSL/DSL_1_B.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_B"

#line 1 "template/template.hpp"
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <bitset>
#include <cctype>
#include <climits>
#include <functional>
#include <cassert>
#include <numeric>
#include <cstring>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define per(i, n) for(int i = (n) - 1; i >= 0; i--)
using ll = long long;
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
constexpr int mod = 1000000007;
using namespace std;
template<class T, class U>
bool chmax(T &a, const U &b){ return a < b ? (a = b, 1) : 0; }
template<class T, class U>
bool chmin(T &a, const U &b){ return a > b ? (a = b, 1) : 0; }
#line 4 "test/aoj/DSL/DSL_1_B.test.cpp"

#line 1 "graph/Weighted-UnionFind.hpp"
template <class T>
struct UnionFindW {
  vector<int> par, rank;
  vector<T> diff_weight;

  UnionFindW(int n = 1, T sum_unity = 0) : n(n), par(n), rank(n), diff_weight(n){
    for(int i = 0; i < n; i++) par[i] = i, rank[i] = 0, diff_weight[i] = sum_unity;
  }
  int root(int x){
    assert(0 <= x && x < n);
    if(par[x] == x){
      return x;
    }else{
      const int r = root(par[x]);
      diff_weight[x] += diff_weight[par[x]];
      return par[x] = r;
    }
  }
  T weight(int x){
    root(x);
    return diff_weight[x];
  }
  bool same(int x, int y){
    return root(x) == root(y);
  }
  bool merge(int x, int y, T w){
    w += weight(x); w -= weight(y);
    x = root(x); y = root(y);
    if(x == y) return false;
    if(rank[x] < rank[y]) swap(x, y), w = -w;
    if(rank[x] == rank[y]) ++rank[x];
    par[y] = x;
    diff_weight[y] = w;
    return true;
  }
  T diff(int x, int y){
    return weight(y) - weight(x);
  }
  private:
  int n;
};
#line 6 "test/aoj/DSL/DSL_1_B.test.cpp"

int main(){
  int n,q;
  cin >> n >> q;
  UnionFindW<int> tree(n);
  rep(i, q){
    int t; cin >> t;
    if(!t){
      int x,y,z;
      cin >> x >> y >> z;
      tree.merge(x, y, z);
    }else{
      int x,y;
      cin >> x >> y;
      if(!tree.same(x, y)) cout << "?\n";
      else cout << tree.diff(x, y) << "\n";
    }
  }
}