#375421 (cLay) No.168 ものさし

• 問題: No.168 ものさし
• ユーザー: tails
• 提出日時: 2019-09-04 00:42:50
• 言語: cLay (20240714-1)
• 結果: AC
• 実行時間: 59 ms / 2,000 ms
• コード長: 359 bytes
• コンパイル時間: 2,908 ms
• コンパイル使用メモリ: 179,512 KB
• 実行使用メモリ: 15,232 KB
• 最終ジャッジ日時: 2024-07-05 13:23:20
• 合計ジャッジ時間: 4,267 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	13 ms; 6,144 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	3 ms; 5,376 KB
testcase_11	AC	13 ms; 5,888 KB
testcase_12	AC	40 ms; 11,648 KB
testcase_13	AC	57 ms; 14,976 KB
testcase_14	AC	57 ms; 15,104 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	2 ms; 5,376 KB
testcase_18	AC	4 ms; 5,376 KB
testcase_19	AC	56 ms; 14,720 KB
testcase_20	AC	56 ms; 15,232 KB
testcase_21	AC	59 ms; 15,232 KB
testcase_22	AC	58 ms; 15,232 KB

ソースコード

ll n,x[1000],y[1000],k,m,r;
pair<ll,pair<ll,ll>> a[600000];
unionFind u;
{
	rd(n,(x,y)(n));
	rep(i,n)rep(j,i)a[m++]={(x[i]-x[j])**2+(y[i]-y[j])**2,{j,i}};
	sort(a,a+m);
	u.walloc(n);
	u.init();
	for(;u.connect(a[k].second.first,a[k].second.second),u.get(0)!=u.get(n-1);)++k;
	r=2**31-1;
	rep(i,31)if((r-2**(30-i))**2>=a[k].first)r-=2**(30-i);
	wt(r/+10*10);
}