結果
問題 | No.2179 Planet Traveler |
ユーザー |
|
提出日時 | 2023-03-16 21:57:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 191 ms / 3,000 ms |
コード長 | 1,725 bytes |
コンパイル時間 | 612 ms |
コンパイル使用メモリ | 88,268 KB |
最終ジャッジ日時 | 2025-02-11 12:01:28 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:49:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 49 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:50:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 50 | for (i=0; i<n; i++) scanf("%d %d %d", &xs[i], &ys[i], &ts[i]); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include<stdio.h>#include<string.h>#include<stdlib.h>#include <map>#include <vector>#include <queue>#include <deque>#include <set>#include <stack>#include <algorithm>#include <array>#include <unordered_set>#include <unordered_map>#include <string>using namespace std;bool rcmp(int a, int b) { return a>b; }typedef long long LL;int xs[804];int ys[804];int ts[804];char mk[804];LL dis[804][804];LL xd[804];LL inf;LL mysqrt(LL v) {LL r=0, nr;LL d=1; d<<=30;while(d) {while(1) {nr=r+d;if (inf/nr<=nr) break;if (nr*nr>v) break;r=nr;}d>>=1;}return r;}int main() {int n, i, mi, j;LL r, nr, d, md;LL dx, dy, dd;inf=1; inf<<=62;scanf("%d", &n);for (i=0; i<n; i++) scanf("%d %d %d", &xs[i], &ys[i], &ts[i]);dx=xs[0]-xs[n-1];dy=ys[0]-ys[n-1];d=dx*dx+dy*dy;for (i=0; i<n; i++) {for (j=i+1; j<n; j++) {if (ts[i]==ts[j]) {dx=xs[i]-xs[j]; dy=ys[i]-ys[j];dd=dx*dx+dy*dy;} else {dx=xs[i]*xs[i]+ys[i]*ys[i];dy=xs[j]*xs[j]+ys[j]*ys[j];dd=mysqrt(dx*dy*4); // <=dd=dx+dy-dd;}dis[i][j]=dis[j][i]=dd;}}for (i=0; i<n; i++) { xd[i]=d+1; mk[i]=0; } xd[0]=0;r=0;while(1) {md=d+1; mi=-1;for (i=0; i<n; i++) if (mk[i]==0&&md>xd[i]) { md=xd[i]; mi=i; }if (mi==-1) break;r=max(r, md); if (mi==n-1) break;mk[mi]=1;for (i=0; i<n; i++) if (mk[i]==0) xd[i]=min(xd[i], dis[mi][i]);}printf("%lld\n", r);return 0;}