test/aoj/DSL_1_A.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_A

Depends on

• Union-Find (src/DataStructure/UnionFind.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_A
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include "src/DataStructure/UnionFind.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int n, q;
 cin >> n >> q;
 UnionFind uf(n);
 for (int i= 0; i < q; i++) {
  int c, x, y;
  cin >> c >> x >> y;
  if (c) cout << uf.connected(x, y) << "\n";
  else uf.unite(x, y);
 }
 return 0;
}

#line 1 "test/aoj/DSL_1_A.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_A
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#line 2 "src/DataStructure/UnionFind.hpp"
#include <vector>
#include <algorithm>
class UnionFind {
 std::vector<int> par;
public:
 UnionFind(int n): par(n, -1) {}
 int leader(int u) { return par[u] < 0 ? u : par[u]= leader(par[u]); }
 bool unite(int u, int v) {
  if ((u= leader(u)) == (v= leader(v))) return false;
  if (par[u] > par[v]) std::swap(u, v);
  return par[u]+= par[v], par[v]= u, true;
 }
 bool connected(int u, int v) { return leader(u) == leader(v); }
 int size(int u) { return -par[leader(u)]; }
};
#line 6 "test/aoj/DSL_1_A.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int n, q;
 cin >> n >> q;
 UnionFind uf(n);
 for (int i= 0; i < q; i++) {
  int c, x, y;
  cin >> c >> x >> y;
  if (c) cout << uf.connected(x, y) << "\n";
  else uf.unite(x, y);
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_small_00.in	AC	5 ms	4 MB
g++-13	00_small_01.in	AC	4 ms	4 MB
g++-13	01_rand_00.in	AC	4 ms	4 MB
g++-13	01_rand_01.in	AC	4 ms	4 MB
g++-13	01_rand_02.in	AC	4 ms	4 MB
g++-13	01_rand_03.in	AC	4 ms	4 MB
g++-13	01_rand_04.in	AC	4 ms	4 MB
g++-13	01_rand_05.in	AC	4 ms	4 MB
g++-13	02_linear_00.in	AC	4 ms	4 MB
g++-13	02_linear_01.in	AC	5 ms	4 MB
g++-13	02_linear_02.in	AC	6 ms	4 MB
g++-13	02_linear_03.in	AC	7 ms	4 MB
g++-13	03_grid_00.in	AC	4 ms	4 MB
g++-13	03_grid_01.in	AC	4 ms	4 MB
g++-13	03_grid_02.in	AC	4 ms	4 MB
g++-13	03_grid_03.in	AC	4 ms	4 MB
g++-13	03_grid_04.in	AC	4 ms	4 MB
g++-13	03_grid_05.in	AC	4 ms	4 MB
g++-13	03_grid_06.in	AC	4 ms	4 MB
g++-13	03_grid_07.in	AC	4 ms	4 MB
g++-13	03_grid_08.in	AC	4 ms	4 MB
g++-13	04_critical_00.in	AC	7 ms	4 MB
g++-13	04_critical_01.in	AC	7 ms	4 MB
g++-13	05_groups_00.in	AC	11 ms	4 MB
g++-13	05_groups_01.in	AC	12 ms	4 MB
g++-13	05_groups_02.in	AC	11 ms	4 MB
g++-13	05_groups_03.in	AC	11 ms	4 MB
g++-13	05_groups_04.in	AC	11 ms	4 MB
g++-13	06_randmax_00.in	AC	4 ms	4 MB
g++-13	06_randmax_01.in	AC	12 ms	4 MB
g++-13	06_randmax_02.in	AC	15 ms	4 MB
g++-13	06_randmax_03.in	AC	20 ms	4 MB
clang++-18	00_small_00.in	AC	5 ms	4 MB
clang++-18	00_small_01.in	AC	5 ms	4 MB
clang++-18	01_rand_00.in	AC	4 ms	4 MB
clang++-18	01_rand_01.in	AC	4 ms	4 MB
clang++-18	01_rand_02.in	AC	4 ms	4 MB
clang++-18	01_rand_03.in	AC	4 ms	4 MB
clang++-18	01_rand_04.in	AC	4 ms	4 MB
clang++-18	01_rand_05.in	AC	4 ms	4 MB
clang++-18	02_linear_00.in	AC	4 ms	4 MB
clang++-18	02_linear_01.in	AC	4 ms	4 MB
clang++-18	02_linear_02.in	AC	6 ms	4 MB
clang++-18	02_linear_03.in	AC	7 ms	4 MB
clang++-18	03_grid_00.in	AC	4 ms	4 MB
clang++-18	03_grid_01.in	AC	4 ms	4 MB
clang++-18	03_grid_02.in	AC	4 ms	4 MB
clang++-18	03_grid_03.in	AC	4 ms	4 MB
clang++-18	03_grid_04.in	AC	4 ms	4 MB
clang++-18	03_grid_05.in	AC	4 ms	4 MB
clang++-18	03_grid_06.in	AC	4 ms	4 MB
clang++-18	03_grid_07.in	AC	4 ms	4 MB
clang++-18	03_grid_08.in	AC	4 ms	4 MB
clang++-18	04_critical_00.in	AC	7 ms	4 MB
clang++-18	04_critical_01.in	AC	7 ms	4 MB
clang++-18	05_groups_00.in	AC	12 ms	4 MB
clang++-18	05_groups_01.in	AC	11 ms	4 MB
clang++-18	05_groups_02.in	AC	11 ms	4 MB
clang++-18	05_groups_03.in	AC	11 ms	4 MB
clang++-18	05_groups_04.in	AC	11 ms	4 MB
clang++-18	06_randmax_00.in	AC	5 ms	4 MB
clang++-18	06_randmax_01.in	AC	12 ms	4 MB
clang++-18	06_randmax_02.in	AC	16 ms	4 MB
clang++-18	06_randmax_03.in	AC	21 ms	4 MB

Back to top page