結果
問題 | No.556 仁義なきサルたち |
ユーザー |
![]() |
提出日時 | 2017-08-11 23:38:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 18 ms / 2,000 ms |
コード長 | 1,528 bytes |
コンパイル時間 | 1,550 ms |
コンパイル使用メモリ | 171,120 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-12 22:05:50 |
合計ジャッジ時間 | 2,606 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; struct Monkey { int boss; int num; int id; vector<int> members; }; int A[10007] = {}; int B[10007] = {}; Monkey monkeys[10007] = {}; // bがaチームにマージされる void merge(int a, int b) { monkeys[a].num += monkeys[b].num; for (auto v : monkeys[b].members) { monkeys[a].members.push_back(v); monkeys[v].boss = a; monkeys[v].num = monkeys[a].num; } } int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N >> M; for (int i = 0; i < N; i++) { cin >> A[i] >> B[i]; } for (int i = 1; i <= N; i++) { monkeys[i].boss = i; monkeys[i].num = 1; monkeys[i].id = i; monkeys[i].members.push_back(i); } for (int i = 0; i < N; i++) { int a = A[i]; int b = B[i]; int boss_a = monkeys[a].boss; int boss_b = monkeys[b].boss; if (boss_a == boss_b) { continue; } else if (monkeys[boss_a].num > monkeys[boss_b].num) { merge(boss_a, boss_b); } else if (monkeys[boss_a].num < monkeys[boss_b].num) { merge(boss_b, boss_a); } else { if (monkeys[boss_a].id < monkeys[boss_b].id) { merge(boss_a, boss_b); } else { merge(boss_b, boss_a); } } } for (int i = 1; i <= N; i++) { cout << monkeys[i].boss << endl; } return 0; }