結果
問題 | No.556 仁義なきサルたち |
ユーザー |
![]() |
提出日時 | 2017-08-13 09:13:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 1,930 bytes |
コンパイル時間 | 1,856 ms |
コンパイル使用メモリ | 174,664 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-13 08:38:04 |
合計ジャッジ時間 | 2,995 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) #define fore(i,a) for(auto &i:a) #pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } //--------------------------------------------------------------------------------------------------- struct UnionFind {vector<int> par, cnt; UnionFind(int NV) { par.clear(); cnt.resize(NV, 1); rep(i, 0, NV) par.push_back(i); } void reset() { rep(i, 0, cnt.size()) cnt[i] = 1; rep(i, 0, par.size()) par[i] = i; } int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); } void operator()(int x, int y) {x = operator[](x); y = operator[](y); if (x != y) par[x] = y, cnt[y] += cnt[x];}}; /*--------------------------------------------------------------------------------------------------- ∧_∧ ∧_∧ (´<_` ) Welcome to My Coding Space! ( ´_ゝ`) / ⌒i / \ | | / / ̄ ̄ ̄ ̄/ | __(__ニつ/ _/ .| .|____ \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ int N, M; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; UnionFind uf(N); rep(i, 0, M) { int A, B; cin >> A >> B; A--; B--; if (uf[A] != uf[B]) { int a = uf[A], b = uf[B]; if (uf.cnt[a] < uf.cnt[b]) uf(a, b); else if (uf.cnt[a] > uf.cnt[b]) uf(b, a); else { if(uf[a] < uf[b]) uf(b, a); else uf(a, b); } } } rep(i, 0, N) printf("%d\n", uf[i] + 1); }