QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#626102 | #7003. Rikka with Minimum Spanning Trees | ucup-team5071# | WA | 0ms | 3784kb | C++20 | 3.6kb | 2024-10-09 23:11:16 | 2024-10-09 23:11:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long double lf;
struct kkk{
int x,tx,y,ty;
// x,y,
// t=0 说明在那个点的左边的边上
// t=1 说明在点上
lf len;
bool operator<(kkk k1)const{
return len>k1.len;
}
};
const lf eps=1e-3;
lf read(){
int x;cin>>x;return (lf)x;
}
lf cal(lf h1,lf h2,lf s,lf t){
if(h1>h2)swap(h1,h2);
if(s>t)swap(s,t);
if((s>=h1-eps&&t<=h2+eps)){
if(fabs(h1-h2)<eps)return 1.;
else {
lf delta=h2-h1;
lf len=sqrt(1.+delta*delta);
return len/delta*(t-s);
}
}
else return -1.;
}
const lf inf=1e18;
lf dis[52][2][52][2];
lf solve(){
int n;cin>>n;
vector<lf>a(n+1);
for(int i=0;i<=n;i++)a[i]=read();
for(int i=0;i<=n;i++){
for(int x=0;x<2;x++)
for(int j=0;j<=n;j++)
for(int y=0;y<2;y++)dis[i][x][j][y]=inf;
}
priority_queue<kkk,vector<kkk>> qu;
auto push = [&](int x,int tx,int y,int ty,lf len){
if(dis[x][tx][y][ty]==inf){
qu.push(kkk{x,tx,y,ty,len});
qu.push(kkk{y,ty,x,tx,len});
}
};
// t=0 说明在那个点的左边的边上
// t=1 说明在点上
push(0,1,n,1,0);
lf ans=inf;
while(!qu.empty()){
kkk k1=qu.top();qu.pop();
int x=k1.x,y=k1.y,tx=k1.tx,ty=k1.ty,len=k1.len;
cout<<"x="<<x<<" y="<<y<<" tx="<<tx<<" ty="<<ty<<" len="<<len<<endl;
if(dis[x][tx][y][ty]!=inf)continue;
dis[x][tx][y][ty]=len;
if(a[x]==a[y])push(x,1,y,1,len);
if(tx==1&&ty==1){
auto go = [&](int x,int xt,int y,int yt,int to){//x is on point x->xt (y->yt)
if(lf d =cal(a[y],a[yt],a[x],a[xt]);d>0)push(xt,1,to,0,len+d);
};
auto solve=[&](){
if(x>0){// <-x
go(x,x-1,y,y,y);
if(y>0)go(x,x-1,y,y-1,y);
if(y<n)go(x,x-1,y,y+1,y+1);
}
if(x<n){// x->
go(x,x+1,y,y,y);
if(y>0)go(x,x+1,y,y-1,y);
if(y<n)go(x,x+1,y,y+1,y+1);
}
};
solve();
swap(x,y);
swap(tx,ty);
solve();
}
else {
auto go = [&](int x,int xt,int y,int yt,int to){//x is on point x->xt (y->yt)
if(lf d =cal(a[y],a[yt],a[x],a[xt]);d>0)push(xt,1,to,0,len+d);
};
if(tx==0){
swap(x,y);
swap(tx,ty);
}
{// x is on point
if(x>0){// <-x
go(x,x-1,y,y,y);
}
if(x<n){// x->
go(x,x+1,y,y,y);
}
}
swap(x,y);
swap(tx,ty);
{// x is on edge
if(x>0){//x-> y->
}
}
}
}
for(int i=0;i<=n;i++)ans=min(ans,dis[i][1][i][1]*2);
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(15);
int T;cin>>T;
while(T--)solve();
}
/*
4
4
0 1 1 2 0
4
0 2 1 3 0
4
0 1 2 1 0
4
0 2 1 2 0
*/
/*
12.128990204491960
22.313624568639947
*/
/*
1
3
0 2 2 0
*/
/*
1
4
0 1 1 2 0
*/
/*
6
4
0 2 0 2 0
6
0 1 0 1 0 1 0
6
0 1 0 2 0 1 0
6
0 2 0 1 0 2 0
6
0 2 0 2 0 1 0
5
0 2 2 0 1 0
17.888
16.970
20.2579
23.545
28.017
21.0732
*/
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3784kb
input:
1 2 100000 123456789 987654321
output:
x=0 y=2 tx=1 ty=1 len=0 x=2 y=0 tx=1 ty=1 len=0
result:
wrong answer 1st lines differ - expected: '575673759', found: 'x=0 y=2 tx=1 ty=1 len=0'