結果
問題 | No.556 仁義なきサルたち |
ユーザー |
![]() |
提出日時 | 2017-08-11 23:38:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 2,008 bytes |
コンパイル時間 | 1,527 ms |
コンパイル使用メモリ | 169,460 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-12 22:05:24 |
合計ジャッジ時間 | 2,342 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;#define REP(i,n) for(int i=0;i<n;++i)#define SORT(name) sort(name.begin(), name.end())#define ZERO(p) memset(p, 0, sizeof(p))#define MINUS(p) memset(p, -1, sizeof(p))#define MOD 1000000007#define INF 1000000000#define MAX_N 10010int N, M;// ランク無し版int par[MAX_N]; // 親の番号int team[MAX_N]; // 各チームの人数// n 要素で初期化void init(int n) {REP(i, n){par[i] = i;team[i] = 1;} // はじめは全部の頂点が根}// 木の根を求めるint root(int x) {if(par[x] == x) { return x; } // 根else { return par[x] = root(par[x]); } // 経路圧縮}// x と y が同じ集合に属するか否かbool same(int x, int y) {return root(x) == root(y);}// x と y の属する集合を併合void unite(int x, int y) {x = root(x);y = root(y);if(x == y) { return; }par[x] = y;}int main(){cin >> N >> M;init(N);REP(i, M) {int a, b;cin >> a >> b;a--;b--;int winner, loser;//printf("a: %d b: %d\n", a, b);if(root(a) == root(b)) {// 同じチームcontinue;}if(team[root(a)] == team[root(b)]) {// 同数なら優先度を見るwinner = min(root(a), root(b));loser = max(root(a), root(b));} else {// 人数を見るif(team[root(a)] > team[root(b)]) {winner = root(a);loser = root(b);} else {winner = root(b);loser = root(a);}}unite(loser, winner);team[winner] += team[loser];//printf("winner %d loser %d team[%d]: %d team[%d]: %d\n",// winner, loser, winner, team[winner], loser, team[loser]);}REP(i, N) {printf("%d\n", root(i) + 1);}return 0;}