結果
問題 | No.1639 最小通信路 |
ユーザー |
|
提出日時 | 2021-08-06 22:10:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 14 ms / 2,000 ms |
コード長 | 1,040 bytes |
コンパイル時間 | 1,625 ms |
コンパイル使用メモリ | 170,060 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-17 02:10:55 |
合計ジャッジ時間 | 3,352 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 43 |
ソースコード
#include <bits/stdc++.h> #define rep(i, l, r) for (int i = (l); i < (r); i++) using namespace std; typedef long long ll; const int MAX_N = 100010; int par[MAX_N]; int rnk[MAX_N]; int siz[MAX_N]; void init(int n) { rep(i,0,n) { par[i] = i; rnk[i] = 0; siz[i] = 1; } } int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; int s = siz[x] + siz[y]; if (rnk[x] < rnk[y]) { par[x] = y; } else { par[y] = x; if (rnk[x] == rnk[y]) rnk[x]++; } siz[find(x)] = s; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return siz[find(x)]; } int main() { int N, a, b; cin >> N; init(N); string C, ans = ""; rep(i, 0, N * (N - 1) / 2) { cin >> a >> b >> C; unite(--a, --b); if (ans == "" && size(a) == N) ans = C; } cout << ans << endl; }