QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#626102#7003. Rikka with Minimum Spanning Treesucup-team5071#WA 0ms3784kbC++203.6kb2024-10-09 23:11:162024-10-09 23:11:19

Judging History

你现在查看的是最新测评结果

  • [2024-10-09 23:11:19]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3784kb
  • [2024-10-09 23:11:16]
  • 提交

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'