結果
問題 | No.3024 全単射的 |
ユーザー |
|
提出日時 | 2025-02-14 22:32:21 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 438 ms / 5,000 ms |
コード長 | 1,197 bytes |
コンパイル時間 | 6,190 ms |
コンパイル使用メモリ | 333,840 KB |
実行使用メモリ | 28,288 KB |
最終ジャッジ日時 | 2025-02-14 22:33:15 |
合計ジャッジ時間 | 9,508 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> // using mint = atcoder::static_modint<998244353>; // //using mint = atcoder::static_modint<1000000007>; using namespace std; using namespace atcoder; using ld = long double; using ll = long long; #define mp(a,b) make_pair(a,b) #define rep(i,s,n) for(int i=s; i<(int)n; i++) const vector<int> dx{1,0,-1,0},dy{0,1,0,-1}; int main(){ ll n,m;cin >> n >> m; vector<ll> x(n),y(n); set<ll> S; rep(i,0,n){ cin >> x[i] >> y[i]; S.insert(x[i]); S.insert(y[i]); } map<ll,int> f; auto itr=S.begin(); int k=0; while(itr!=S.end()){ f[*itr]=k; k++,itr++; } rep(i,0,n)x[i]=f[x[i]],y[i]=f[y[i]]; dsu uf(k); vector<int> cnt(k); rep(i,0,n){ if(uf.same(x[i],y[i])){ int z=uf.leader(x[i]); cnt[z]++; } else{ x[i]=uf.leader(x[i]),y[i]=uf.leader(y[i]); int c=cnt[x[i]]+cnt[y[i]]+1; uf.merge(x[i],y[i]); int z=uf.leader(x[i]); cnt[z]=c; } } int ans=0; rep(i,0,k)if(i==uf.leader(i)){ ans+=min(uf.size(i),cnt[i]); } cout << ans; }