結果
問題 | No.1390 Get together |
ユーザー | IKyopro |
提出日時 | 2021-02-13 15:41:56 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 71 ms / 2,000 ms |
コード長 | 1,514 bytes |
コンパイル時間 | 2,178 ms |
コンパイル使用メモリ | 204,580 KB |
実行使用メモリ | 13,292 KB |
最終ジャッジ日時 | 2023-09-28 00:09:47 |
合計ジャッジ時間 | 6,007 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 3 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 3 ms
4,380 KB |
testcase_10 | AC | 1 ms
4,376 KB |
testcase_11 | AC | 1 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 1 ms
4,380 KB |
testcase_14 | AC | 2 ms
4,380 KB |
testcase_15 | AC | 1 ms
4,380 KB |
testcase_16 | AC | 42 ms
10,108 KB |
testcase_17 | AC | 63 ms
13,084 KB |
testcase_18 | AC | 42 ms
10,120 KB |
testcase_19 | AC | 62 ms
13,108 KB |
testcase_20 | AC | 62 ms
13,236 KB |
testcase_21 | AC | 61 ms
13,176 KB |
testcase_22 | AC | 51 ms
12,176 KB |
testcase_23 | AC | 54 ms
12,432 KB |
testcase_24 | AC | 52 ms
12,220 KB |
testcase_25 | AC | 62 ms
13,196 KB |
testcase_26 | AC | 68 ms
13,128 KB |
testcase_27 | AC | 65 ms
13,292 KB |
testcase_28 | AC | 71 ms
13,176 KB |
testcase_29 | AC | 69 ms
13,216 KB |
testcase_30 | AC | 63 ms
13,264 KB |
testcase_31 | AC | 65 ms
13,180 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template <class T> using vec = vector<T>; template <class T> using vvec = vector<vec<T>>; template<class T> bool chmin(T& a,T b){if(a>b) {a = b; return true;} return false;} template<class T> bool chmax(T& a,T b){if(a<b) {a = b; return true;} return false;} #define rep(i,n) for(int i=0;i<(n);i++) #define drep(i,n) for(int i=(n)-1;i>=0;i--) #define all(x) (x).begin(),(x).end() #define debug(x) cerr << #x << " = " << (x) << endl; class UnionFind{ private: vec<int> p,s; int cnt; public: UnionFind(){} UnionFind(int N):cnt(N),s(N,1),p(N){ iota(p.begin(),p.end(),0); } int find(int x){ if(p[x]==x) return x; else return p[x] = find(p[x]); } void unite(int x,int y){ x = find(x); y = find(y); if(x==y) return; if(s[x]>s[y]) swap(x,y); p[x] = y; s[y] += s[x]; cnt--; } int operator[](const int x){return find(x);} bool is_same_set(int x,int y) {return find(x)==find(y);} int size(int x) {return s[find(x)];} int compnents_number(){return cnt;} }; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N,M; cin >> N >> M; vvec<int> C(N); rep(i,N){ int b,c; cin >> b >> c; b--,c--; C[c].push_back(b); } UnionFind uf(M); for(auto& v:C){ for(auto& x:v){ uf.unite(v[0],x); } } cout << M-uf.compnents_number() << "\n"; }