結果
問題 | No.1390 Get together |
ユーザー |
![]() |
提出日時 | 2021-02-12 23:14:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,834 bytes |
コンパイル時間 | 2,344 ms |
コンパイル使用メモリ | 205,888 KB |
最終ジャッジ日時 | 2025-01-18 19:44:55 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 16 WA * 13 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <class A, class B> bool cmin(A& a, B b) { return a > b && (a = b, true); }template <class A, class B> bool cmax(A& a, B b) { return a < b && (a = b, true); }class UnionFind {private:long N;vector<long> PS;public:UnionFind() : N(0) {}UnionFind(long n) : N(n), PS(n, -1) {}bool unite(long a, long b) {long x = root(a), y = root(b);if (x == y) return false;if (-PS.at(x) < -PS.at(y)) swap(x, y);PS.at(x) += PS.at(y);PS.at(y) = x;return true;}bool same(long a, long b) { return root(a) == root(b); }long root(long a) {if (PS.at(a) < 0) return a;return PS.at(a) = root(PS.at(a));}long size(long a) { return -PS.at(root(a)); }vector<vector<long>> groups() {vector<long> B(N), S(N);for (long i = 0; i < N; i++) {B.at(i) = root(i);S.at(B.at(i))++;}vector<vector<long>> ret(N);for (long i = 0; i < N; i++) {ret.at(i).reserve(S.at(i));}for (long i = 0; i < N; i++) {ret.at(B.at(i)).push_back(i);}auto f = [&](const vector<long> &v) { return v.empty(); };ret.erase(remove_if(ret.begin(), ret.end(), f), ret.end());return ret;}};signed main() {cin.tie(nullptr)->sync_with_stdio(false);long N, M;cin >> N >> M;vector<pair<long, long>> V(N);for (long i = 0; i < N; i++) {long a, b;cin >> a >> b, a--, b--;V.at(i) = {a, b};}vector<vector<long>> G(N);for (const auto& [a, b] : V) G.at(b).push_back(a);long ans = 0;UnionFind UF(M);for (const auto& g : G) {if ((long)g.size() < 2) continue;long r = UF.root(g.front());for (const auto& a : g) {if (UF.root(a) != r) {UF.unite(a, g.front());ans++;}}}cout << ans << '\n';}