結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 2022-07-30 16:24:46 |
言語 | cLay (20241019-1) |
結果 |
AC
|
実行時間 | 8 ms / 1,000 ms |
コード長 | 956 bytes |
コンパイル時間 | 2,641 ms |
実行使用メモリ | 6,956 KB |
スコア | 7,540,464 |
最終ジャッジ日時 | 2022-07-30 16:25:03 |
合計ジャッジ時間 | 4,425 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
ll n,m,a[108],b[108];vector<vector<int>> y(108);void out1(ll i){if(i<n){wt(1,i+1);}else{wt(2,i-n+1);}}void outdfs(ll i,ll p){out1(i);for(int x:y[i]){if(x!=p){outdfs(x,i);out1(i);}}}{rd(n,m,(a,b)(n));unionFind u('w',n+m);rep(o,m+1){vector<pair<ll,pair<ll,ll>>> v;rep(i,n+o){rep(j,i){ll w=(i<n?5:1)*(j<n?5:1);v.push_back({w*((a[i]-a[j])**2+(b[i]-b[j])**2),{i,j}});}}sort(v.begin(),v.end());u.init();if(o<m){ll li=0,lj=0;for(auto x:v){ll i=x.second.first;ll j=x.second.second;if(u(i)!=u(j)){u(i,j);li=i;lj=j;}}a[n+o]=(a[li]+a[lj])/2;b[n+o]=(b[li]+b[lj])/2;}else{for(auto x:v){ll i=x.second.first;ll j=x.second.second;if(u(i)!=u(j)){u(i,j);y[i].push_back(j);y[j].push_back(i);}}rep(i,n,n+m){wt(a[i],b[i]);}wt((n+m)*2-1);outdfs(0,0);}}}