結果

問題 No.1390 Get together
ユーザー okok
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0