結果
問題 | No.1390 Get together |
ユーザー |
|
提出日時 | 2021-02-12 21:34:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 150 ms / 2,000 ms |
コード長 | 903 bytes |
コンパイル時間 | 790 ms |
コンパイル使用メモリ | 72,960 KB |
実行使用メモリ | 13,556 KB |
最終ジャッジ日時 | 2024-07-19 20:30:47 |
合計ジャッジ時間 | 4,291 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
コンパイルメッセージ
a.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
ソースコード
#line 1 "a.cpp"#include<iostream>#include<vector>using namespace std;#line 2 "/home/kotatsugame/library/datastructure/UF.cpp"struct UF{int n;vector<int>parent,rank;UF(int n_=0):n(n_),parent(n_),rank(n_,1){for(int i=0;i<n_;i++)parent[i]=i;}int find(int a){return parent[a]!=a?parent[a]=find(parent[a]):a;}bool same(int a,int b){return find(a)==find(b);}bool unite(int a,int b){a=find(a),b=find(b);if(a==b)return false;if(rank[a]<rank[b]){parent[a]=b;rank[b]+=rank[a];}else{parent[b]=a;rank[a]+=rank[b];}return true;}int size(int a){return rank[find(a)];}};#line 5 "a.cpp"int N,M;main(){cin>>N>>M;UF uf(M);vector<vector<int> >G(N);for(int i=0;i<N;i++){int b,c;cin>>b>>c;G[c-1].push_back(b-1);}int ans=0;for(vector<int>&v:G){for(int i=1;i<v.size();i++)ans+=uf.unite(v[0],v[i]);}cout<<ans<<endl;}