結果
問題 | No.1390 Get together |
ユーザー |
|
提出日時 | 2021-02-12 21:55:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 172 ms / 2,000 ms |
コード長 | 2,045 bytes |
コンパイル時間 | 1,171 ms |
コンパイル使用メモリ | 94,420 KB |
実行使用メモリ | 23,424 KB |
最終ジャッジ日時 | 2024-07-19 21:14:27 |
合計ジャッジ時間 | 4,777 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include<iostream>#include<string>#include<iomanip>#include<cmath>#include<vector>#include<algorithm>#include<utility>using namespace std;#define int long long#define endl "\n"constexpr long long INF = (long long)1e18;constexpr long long MOD = 1'000'000'007;struct fast_io {fast_io(){std::cin.tie(nullptr);std::ios::sync_with_stdio(false);};} fio;class union_find{int _setnum;vector<int> par, nume;public:union_find(){}union_find(int x){par.resize(x);nume.resize(x);init();}~union_find(){//}void clear(){_setnum = 0;par.clear();nume.clear();}void init(){_setnum = par.size();for(int i = 0; i < par.size(); i++){par[i] = i;nume[i] = 1;}}void resize(int x){par.resize(x);nume.resize(x);init();}int find(int x){return par[x] == x ? x : par[x] = find(par[x]);}void unite(int x, int y){x = find(x);y = find(y);if(x == y)return;_setnum--;if(nume[x] > nume[y]) std::swap(x,y);par[x] = y;nume[y] += nume[x];}bool same(int x, int y){return find(x) == find(y);}int numel(int x){return nume[find(x)];}int size(){return par.size();}int setnum(){return _setnum;}};signed main(){cout<<fixed<<setprecision(10);int N, M;int ans = 0;union_find uf, uf2;vector<bool> used;vector<int> con;vector<vector<int>> col;cin>>N>>M;uf.resize(N + M);used.resize(M + N);uf2.resize(N);col.resize(M);for(int i = 0; i < N; i++){int b, c;cin>>b>>c;b--;c--;uf.unite(b, M + c);if(col[b].size()) uf2.unite(c, col[b].back());col[b].push_back(c);}for(int i = 0; i < M; i++){if(used[uf.find(i)]) continue;if(!col[i].size()) continue;used[uf.find(i)] = true;ans += uf.numel(i) - uf2.numel(col[i].back()) - 1;}cout<<ans<<endl;return 0;}