結果
問題 | No.1639 最小通信路 |
ユーザー |
|
提出日時 | 2021-08-06 22:00:21 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 114 ms / 2,000 ms |
コード長 | 1,007 bytes |
コンパイル時間 | 204 ms |
コンパイル使用メモリ | 7,296 KB |
実行使用メモリ | 12,544 KB |
最終ジャッジ日時 | 2024-09-17 01:57:59 |
合計ジャッジ時間 | 5,623 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 43 |
コンパイルメッセージ
Syntax OK
ソースコード
def lscan; gets.split.map(&:to_i); end n = gets.to_i # class Unionfind { # public: # vector<int> data; # explicit Unionfind(int size) : data(size, -1) {} # bool connect(int x, int y) { # x = root(x); # y = root(y); # if (x != y) { # if (data[y] < data[x]) # swap(x, y); # data[x] += data[y]; # data[y] = (int)x; # } # return x != y; # } # inline bool same(int x, int y) { return root(x) == root(y); } # inline int root(int x) { return (int)(data[x] < 0 ? x : data[x] = root(data[x])); } # inline int size(int x) { return -data[root(x)]; } # }; uf = [-1]*n root = lambda do |x| uf[x] < 0 ? x : (uf[x] = root.call(uf[x])) end conn = lambda do |x, y| x = root.call(x) y = root.call(y) if x != y x,y = y,x if uf[y] < uf[x] uf[x] += uf[y] uf[y] = x end x != y end max = 0 (n*(n-1)/2).times do a,b,c = lscan a -= 1 b -= 1 max = [c, max].max if conn.call(a,b) if -uf[root.call(a)] == n p max exit end end