結果
問題 |
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); }