結果
問題 | No.1390 Get together |
ユーザー |
|
提出日時 | 2021-02-12 23:41:18 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 61 ms / 2,000 ms |
コード長 | 1,574 bytes |
コンパイル時間 | 2,835 ms |
コンパイル使用メモリ | 162,220 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-20 01:33:14 |
合計ジャッジ時間 | 5,036 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h>template<class T>void print(const T &t) { std::cout << t << '\n'; }template<class Head, class... Tail>void print(const Head &head, const Tail &... tail) {std::cout << head << ' ';print(tail...);}template<typename T>using v = std::vector<T>;using ll = long long;using std::cin;struct UnionFind {v<int> parent, rank, count;explicit UnionFind(int n) :parent(n, -1), rank(n, 1), count(n, 1) {}int get_root(int n) {if (parent[n] == -1) {return n;} else {return parent[n] = get_root(parent[n]);}}bool is_same(int i, int j) {return get_root(i) == get_root(j);}void merge(int i, int j) {i = get_root(i);j = get_root(j);if (i == j) {return;}if (rank[i] < rank[j]) {std::swap(i, j);}parent[j] = i;rank[i] = std::max(rank[i], rank[j] + 1);count[i] += count[j];}};int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n, m;cin >> n >> m;v<int> col(n, -1);UnionFind uf(m);for (int i = 0; i < n; ++i) {int b, c;cin >> b >> c;b--;c--;if (col[c] != -1) {uf.merge(b, col[c]);}col[c] = b;}int ans = 0;for (int i = 0; i < m; ++i) {if (uf.parent[i] == -1) {ans += uf.count[i] - 1;}}print(ans);}