結果
問題 |
No.556 仁義なきサルたち
|
ユーザー |
|
提出日時 | 2020-07-09 22:38:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 24 ms / 2,000 ms |
コード長 | 1,106 bytes |
コンパイル時間 | 1,926 ms |
コンパイル使用メモリ | 176,344 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-08 14:35:41 |
合計ジャッジ時間 | 3,240 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) using namespace std; using ll = long long ; using P = pair<int,int> ; using pll = pair<long long,long long>; constexpr int INF = 1e9; constexpr long long LINF = 1e17; constexpr int MOD = 1000000007; constexpr double PI = 3.14159265358979323846; int main(){ int n,m; cin >> n >> m; vector<int> boss(n); vector<set<int>> num(n); iota(boss.begin(),boss.end(),0); rep(i,n) num[i].insert(i); rep(i,m){ int a,b; cin >> a >> b; --a;--b; int bossa = boss[a],bossb = boss[b]; if(bossa==bossb) continue; if((int)(num[bossa].size())>(int)(num[bossb].size())){ swap(bossa,bossb); }else if((int)(num[bossa].size())==(int)(num[bossb].size())){ if(bossa<bossb) swap(bossa,bossb); } auto it = num[bossa].begin(); while(it!=num[bossa].end()){ boss[*it] = bossb; num[bossb].insert(*it); it = num[bossa].erase(it); } } rep(i,n) cout << boss[i]+1 << endl; return 0; }