test/verify/structure/aoj-dsl1-b.test.cpp

View this file on GitHub
Last update: 2024-08-21 21:41:37+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_B

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_B"

#include "template/template.hpp"
#include "structure/potentialized-union-find-tree.hpp"

ll op(ll a, ll b) {
  return a + b;
}

ll invop(ll a, ll b) {
  return a - b;
}

ll e() {
  return 0LL;
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, q; cin >> n >> q;

  PotentializedUnionFindTree<ll,op,invop,e> puf(n);
  for(int i=0; i<q; i++) {
    int t; cin >> t;
    int x, y; cin >> x >> y;
    if (t == 0) {
      ll z; cin >> z;
      puf.merge(x,y,-z);
    }
    else if (t == 1) {
      if (puf.same(x,y)) {
        ll diff = puf.diff(y,x);
        cout << diff << endl; 
      }
      else cout << "?" <<  endl;
    }
  }
  return 0;
}

#line 1 "test/verify/structure/aoj-dsl1-b.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_B"

#line 1 "template/template.hpp"
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;}
const int INTINF = 1000001000;
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLINF = 1000000000000000000;
#line 1 "structure/potentialized-union-find-tree.hpp"



#include <vector>

template <typename T, T(*op)(T, T), T(*invop)(T, T), T(*e)()>
struct PotentializedUnionFindTree {
private:
  int n;
  std::vector<int> parent;
  std::vector<int> rank;
  std::vector<T> potential;

public:
  explicit PotentializedUnionFindTree(int _n) : n(_n), parent(_n), rank(_n, 0), potential(_n, e()) {
    for (int i = 0; i < n; ++i) {
      parent[i] = i;
    }
  }
  
  int merge(int a, int b, T d) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    int rootA = leader(a);
    int rootB = leader(b);

    if (rootA == rootB) return rootA;

    T new_potential = invop(potential[a], op(d, potential[b]));

    if (rank[rootA] < rank[rootB]) {  
      std::swap(rootA, rootB);
      new_potential = invop(e(), new_potential);
    }

    parent[rootB] = rootA;
    potential[rootB] = new_potential;

    if (rank[rootA] == rank[rootB]) {
      rank[rootA]++;
    }

    return rootA;
  }

  bool same(int a, int b) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    return leader(a) == leader(b);
  }

  int leader(int a) {
    assert(0 <= a && a < n);
    if (parent[a] != a) {
      int root = leader(parent[a]);
      potential[a] = op(potential[a], potential[parent[a]]);
      parent[a] = root;
    }
    return parent[a];
  }

  int size(int a) {
    assert(0 <= a && a < n);
    int root = leader(a);
    int size = 0;
    for (int i = 0; i < n; ++i) {
      if (leader(i) == root) {
        ++size;
      }
    }
    return size;
  }

  T diff(int a, int b) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    assert(same(a,b));
    return invop(potential[a], potential[b]);
  }
};


#line 5 "test/verify/structure/aoj-dsl1-b.test.cpp"

ll op(ll a, ll b) {
  return a + b;
}

ll invop(ll a, ll b) {
  return a - b;
}

ll e() {
  return 0LL;
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, q; cin >> n >> q;

  PotentializedUnionFindTree<ll,op,invop,e> puf(n);
  for(int i=0; i<q; i++) {
    int t; cin >> t;
    int x, y; cin >> x >> y;
    if (t == 0) {
      ll z; cin >> z;
      puf.merge(x,y,-z);
    }
    else if (t == 1) {
      if (puf.same(x,y)) {
        ll diff = puf.diff(y,x);
        cout << diff << endl; 
      }
      else cout << "?" <<  endl;
    }
  }
  return 0;
}