test/structure/weighted_union_find.aoj_V13_1330.test.cpp

View this file on GitHub
Last update: 2022-12-04 10:55:39+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1330

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1330"

#include <iostream>

#include "macros.hpp"
#include "structure/weightedUnionFind.hpp"

using namespace std;

int main() {
  int N, M;
  while (true) {
    cin >> N >> M;
    if (N == 0 && M == 0) break;
    UnionFind<int> uf(N);
    int l, r, w;
    char q;
    rep(i, M) {
      cin >> q;
      if (q == '!') {
        cin >> l >> r >> w;
        l--, r--;
        uf.merge(l, r, w);
      } else if (q == '?') {
        cin >> l >> r;
        l--, r--;
        if (uf.issame(l, r)) {
          cout << uf.diff(l, r) << endl;
        } else {
          cout << "UNKNOWN" << endl;
        }
      }
    }
  }
}

#line 1 "test/structure/weighted_union_find.aoj_V13_1330.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1330"

#include <iostream>

#line 2 "macros.hpp"
#define rep(i, n) for (int i = 0; i < (n); i++)
#line 2 "structure/weightedUnionFind.hpp"
#include <vector>
using namespace std;

template <typename T = int>
struct UnionFind {
  vector<int> par;
  vector<int> rank;
  vector<T> diff_weight;

  UnionFind(int n = 1, T SUM_UNITY = 0) { init(n, SUM_UNITY); }

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

  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;
    }
  }

  T weight(int x) {
    root(x);
    return diff_weight[x];
  }

  T diff(int x, int y) { return weight(y) - weight(x); }

  bool issame(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;
  }
};
#line 7 "test/structure/weighted_union_find.aoj_V13_1330.test.cpp"

using namespace std;

int main() {
  int N, M;
  while (true) {
    cin >> N >> M;
    if (N == 0 && M == 0) break;
    UnionFind<int> uf(N);
    int l, r, w;
    char q;
    rep(i, M) {
      cin >> q;
      if (q == '!') {
        cin >> l >> r >> w;
        l--, r--;
        uf.merge(l, r, w);
      } else if (q == '?') {
        cin >> l >> r;
        l--, r--;
        if (uf.issame(l, r)) {
          cout << uf.diff(l, r) << endl;
        } else {
          cout << "UNKNOWN" << endl;
        }
      }
    }
  }
}