QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #187252 | #3858. Systematic salesman | Nax_hueux# | WA | 2ms | 16760kb | C++14 | 4.2kb | 2023-09-24 15:47:28 | 2023-09-24 15:47:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=1100;
const double inf=2e9;
int n,newp[N];
struct point {
double x,y;
int id;
}pos[N];
bool cmpx(point a,point b) {
return a.x<b.x;
}
bool cmpy(point a,point b) {
return a.y<b.y;
}
struct tree {
int l,r,dep,mid;
}t[N<<2];
#define ls(k) ((k)<<1)
#define rs(k) ((k)<<1|1)
inline void build(int k,int l,int r,int d) {
t[k].l=l,t[k].r=r,t[k].dep=d;
// printf("tree:[%d,%d] dep:%d\n",l,r,d);
if(l==r) {
newp[pos[l].id]=l;
return ;
}
if(d&1) sort(pos+l,pos+r+1,cmpx);
else sort(pos+l,pos+r+1,cmpy);
int mid=(l+r-1)>>1; t[k].mid=mid;
build(ls(k),l,mid,d+1);
build(rs(k),mid+1,r,d+1);
}
int frm[N][N][2],frmz[N][N];
double s[N][N],f[N][N],z[N][N];
double dis(point a,point b) {
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
#define tll t[ls(ls(k))]
#define tlr t[rs(ls(k))]
#define trl t[ls(rs(k))]
#define trr t[rs(rs(k))]
inline bool cmin(double &x,double y) {
if(x>y) {x=y;return true;}
return false;
}
inline void work(int k) {
if(t[k].r-t[k].l+1==2) {
f[t[k].l][t[k].r]=s[t[k].l][t[k].r];
return ;
} else if(t[k].r-t[k].l+1==3) {
f[t[k].l][t[k].l+1]=s[t[k].l][t[k].l+2]+s[t[k].l+1][t[k].l+2];
f[t[k].l][t[k].l+2]=s[t[k].l][t[k].l+1]+s[t[k].l+1][t[k].l+2];
return ;
}
work(ls(k));
work(rs(k));
int i1,i2,i3;
for(i1=tll.l;i1<=tll.r;i1++) {
for(i2=tlr.l;i2<=tlr.r;i2++) {
for(i3=trl.l;i3<=trl.r;i3++) {
if(cmin(z[i1][i3],f[i1][i2]+s[i2][i3])) frmz[i1][i3]=i2;
}
for(i3=trr.l;i3<=trr.r;i3++) {
if(cmin(z[i1][i3],f[i1][i2]+s[i2][i3])) frmz[i1][i3]=i2;
}
}
for(i2=trl.l;i2<=trl.r;i2++) {
for(i3=trr.l;i3<=trr.r;i3++) {
if(cmin(f[i1][i3],z[i1][i2]+f[i2][i3])) frm[i1][i3][0]=frmz[i1][i3],frm[i1][i3][1]=i2;
}
}
for(i2=trr.l;i2<=trr.r;i2++) {
for(i3=trl.l;i3<=trl.r;i3++) {
if(cmin(f[i1][i3],z[i1][i2]+f[i3][i2])) frm[i1][i3][0]=frmz[i1][i3],frm[i1][i3][1]=i2;
}
}
}
for(i1=tlr.l;i1<=tlr.r;i1++) {
for(i2=tll.l;i2<=tll.r;i2++) {
for(i3=trl.l;i3<=trl.r;i3++) {
if(cmin(z[i1][i3],f[i2][i1]+s[i2][i3])) frmz[i1][i3]=i2;
}
for(i3=trr.l;i3<=trr.r;i3++) {
if(cmin(z[i1][i3],f[i2][i1]+s[i2][i3])) frmz[i1][i3]=i2;
}
}
for(i2=trl.l;i2<=trl.r;i2++) {
for(i3=trr.l;i3<=trr.r;i3++) {
if(cmin(f[i1][i3],z[i1][i2]+f[i2][i3])) frm[i1][i3][0]=frmz[i1][i3],frm[i1][i3][1]=i2;
}
}
for(i2=trr.l;i2<=trr.r;i2++) {
for(i3=trl.l;i3<=trl.r;i3++) {
if(cmin(f[i1][i3],z[i1][i2]+f[i3][i2])) frm[i1][i3][0]=frmz[i1][i3],frm[i1][i3][1]=i2;
}
}
}
}
inline void print(int k,int S,int T) {
if(t[k].r-t[k].l+1==2) {
printf("%d %d ",pos[S].id,pos[T].id);
return ;
} else if(t[k].r-t[k].l+1==3) {
printf("%d %d %d ",pos[S].id,pos[t[k].l].id+pos[t[k].l+1].id+pos[t[k].l+2].id-pos[S].id-pos[T].id,pos[T].id);
return ;
}
if(S<=t[k].mid) {
print(ls(k),S,frm[min(S,T)][max(S,T)][0]);
print(rs(k),frm[min(S,T)][max(S,T)][1],T);
} else {
print(rs(k),S,frm[min(S,T)][max(S,T)][1]);
print(ls(k),frm[min(S,T)][max(S,T)][0],T);
}
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&pos[i].x,&pos[i].y),pos[i].id=i;
if(n==1) {
puts("0\n1");
return 0;
}
build(1,1,n,1);
// for(int i=1;i<=n;i++) printf("%d ",pos[i].id);puts("");
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++) {
s[i][j]=dis(pos[i],pos[j]);
f[i][j]=z[i][j]=inf;
}
work(1);
double mx=inf;
int mxf1,mxf2;
for(int i=t[2].l;i<=t[2].r;i++)
for(int j=t[3].l;j<=t[3].r;j++) {
if(cmin(mx,f[i][j])) mxf1=i,mxf2=j;
}
printf("%lf\n",mx);
print(1,mxf1,mxf2);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 12204kb
input:
8 7 3 2 0 4 5 1 4 8 2 9 9 0 8 6 1
output:
26.383326 7 3 4 2 8 5 1 6
result:
ok correct!
Test #2:
score: 0
Accepted
time: 2ms
memory: 12272kb
input:
20 4 71 52 7 49 15 59 83 12 9 46 6 74 44 89 50 32 10 82 58 11 33 78 72 27 49 64 75 97 0 38 46 91 54 8 70 18 61 79 92
output:
374.883681 1 18 19 13 16 11 5 9 3 6 2 7 15 8 17 10 12 20 4 14
result:
ok correct!
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 16760kb
input:
100 192 64 839 68 846 688 911 133 110 439 592 226 355 364 418 487 402 466 436 425 509 847 542 78 648 404 954 313 726 906 777 922 596 550 159 172 507 651 720 932 575 805 889 193 246 206 175 326 897 464 108 70 790 2 548 624 867 222 743 269 41 98 348 173 49 915 35 939 404 571 371 625 363 758 317 155 90...
output:
8491.452160 31 26 86 1 98 18 93 79 5 45 90 24 23 38 42 57 32 56 85 49 67 41 9 7 10 63 83 62 96 47 39 33 34 48 72 91 60 61 88 11 92 80 99 37 89 36 35 82 19 8 75 28 44 17 71 78 21 50 58 69 97 55 15 20 81 16 74 66 76 87 3 46 54 77 95 68 73 25 52 43 14 84 29 22 4 40 2 27 12 53 100 65 6 30 64 51 13 70 59...
result:
wrong answer you reported 8491.452160000 but the real length of your path is 9099.747110621