test/aoj/DSL_1_B.test.cpp

• View this file on GitHub
• Last update: 2024-09-20 12:04:43+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_B

Depends on

• Union-Find (ポテンシャル) (src/DataStructure/UnionFind_Potentialized.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_B
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64

// ポテンシャルUF
#include <iostream>
#include "src/DataStructure/UnionFind_Potentialized.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int n, q;
 cin >> n >> q;
 UnionFind_Potentialized<int> uf(n);
 for (int i= 0; i < q; i++) {
  int c, x, y;
  cin >> c >> x >> y;
  if (c) {
   if (uf.connected(x, y)) cout << uf.diff(x, y) << "\n";
   else cout << "?\n";
  } else {
   int z;
   cin >> z;
   uf.unite(x, y, z);
  }
 }
 return 0;
}

#line 1 "test/aoj/DSL_1_B.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_B
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64

// ポテンシャルUF
#include <iostream>
#line 2 "src/DataStructure/UnionFind_Potentialized.hpp"
#include <vector>
#include <algorithm>
#include <cassert>
template <class weight_t> class UnionFind_Potentialized {
 std::vector<int> par;
 std::vector<weight_t> val;
public:
 UnionFind_Potentialized(int n): par(n, -1), val(n) {}
 int leader(int u) {
  if (par[u] < 0) return u;
  int r= leader(par[u]);
  if constexpr (std::is_same_v<weight_t, bool>) val[u]= val[u] ^ val[par[u]];
  else val[u]= val[par[u]] + val[u];
  return par[u]= r;
 }
 //  -p(v) + p(u) = w
 bool unite(int u, int v, weight_t w) {
  int a= leader(u), b= leader(v);
  if constexpr (std::is_same_v<weight_t, bool>) w^= val[u] ^ val[v];
  else w= val[v] + w - val[u];
  if (a == b) return w == weight_t();
  if (par[b] > par[a]) std::swap(a, b), w= -w;
  return par[b]+= par[a], par[a]= b, val[a]= w, true;
 }
 bool connected(int u, int v) { return leader(u) == leader(v); }
 int size(int u) { return -par[leader(u)]; }
 weight_t potential(int u) { return leader(u), val[u]; }
 //  -p(v) + p(u)
 weight_t diff(int u, int v) {
  if constexpr (std::is_same_v<weight_t, bool>) return potential(u) ^ potential(v);
  else return -potential(v) + potential(u);
 }
};
#line 8 "test/aoj/DSL_1_B.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int n, q;
 cin >> n >> q;
 UnionFind_Potentialized<int> uf(n);
 for (int i= 0; i < q; i++) {
  int c, x, y;
  cin >> c >> x >> y;
  if (c) {
   if (uf.connected(x, y)) cout << uf.diff(x, y) << "\n";
   else cout << "?\n";
  } else {
   int z;
   cin >> z;
   uf.unite(x, y, z);
  }
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00.in	AC	5 ms	4 MB
g++-13	01_small_00.in	AC	4 ms	4 MB
g++-13	02_corner_00.in	AC	4 ms	4 MB
g++-13	03_general_00.in	AC	4 ms	4 MB
g++-13	04_rand_00.in	AC	4 ms	4 MB
g++-13	04_rand_01.in	AC	4 ms	4 MB
g++-13	04_rand_02.in	AC	4 ms	4 MB
g++-13	04_rand_03.in	AC	4 ms	4 MB
g++-13	04_rand_04.in	AC	4 ms	4 MB
g++-13	04_rand_05.in	AC	4 ms	4 MB
g++-13	04_rand_06.in	AC	4 ms	4 MB
g++-13	04_rand_07.in	AC	4 ms	4 MB
g++-13	05_large_00.in	AC	10 ms	4 MB
g++-13	05_large_01.in	AC	12 ms	4 MB
g++-13	06_maximum_00.in	AC	24 ms	4 MB
g++-13	06_maximum_02.in	AC	24 ms	4 MB
g++-13	07_dense_00.in	AC	6 ms	4 MB
g++-13	07_dense_01.in	AC	8 ms	4 MB
g++-13	07_dense_02.in	AC	14 ms	4 MB
g++-13	07_dense_03.in	AC	24 ms	4 MB
g++-13	08_shell_00.in	AC	43 ms	4 MB
g++-13	09_extreme_line_00.in	AC	43 ms	4 MB
g++-13	09_extreme_same_00.in	AC	44 ms	4 MB
g++-13	09_extreme_same_01.in	AC	45 ms	4 MB
clang++-18	00_sample_00.in	AC	5 ms	4 MB
clang++-18	01_small_00.in	AC	4 ms	4 MB
clang++-18	02_corner_00.in	AC	4 ms	4 MB
clang++-18	03_general_00.in	AC	4 ms	4 MB
clang++-18	04_rand_00.in	AC	4 ms	4 MB
clang++-18	04_rand_01.in	AC	4 ms	4 MB
clang++-18	04_rand_02.in	AC	4 ms	4 MB
clang++-18	04_rand_03.in	AC	4 ms	4 MB
clang++-18	04_rand_04.in	AC	4 ms	4 MB
clang++-18	04_rand_05.in	AC	4 ms	4 MB
clang++-18	04_rand_06.in	AC	4 ms	4 MB
clang++-18	04_rand_07.in	AC	4 ms	4 MB
clang++-18	05_large_00.in	AC	10 ms	4 MB
clang++-18	05_large_01.in	AC	12 ms	4 MB
clang++-18	06_maximum_00.in	AC	23 ms	4 MB
clang++-18	06_maximum_02.in	AC	24 ms	4 MB
clang++-18	07_dense_00.in	AC	6 ms	4 MB
clang++-18	07_dense_01.in	AC	8 ms	4 MB
clang++-18	07_dense_02.in	AC	15 ms	4 MB
clang++-18	07_dense_03.in	AC	23 ms	4 MB
clang++-18	08_shell_00.in	AC	42 ms	4 MB
clang++-18	09_extreme_line_00.in	AC	42 ms	4 MB
clang++-18	09_extreme_same_00.in	AC	45 ms	4 MB
clang++-18	09_extreme_same_01.in	AC	45 ms	4 MB

Back to top page