【Codeforces 704E】Iron Man

Author Avatar
mrsrz 1月 21, 2020

树链剖分，计算几何，扫描线。

题目大意：

给定一棵树，有 $m$ 个人，每个人出现的时刻为 $t_i$，以每一单位时间 $c_i$ 条边的速度从 $u_i$ 向 $v_i$ 匀速运动，到终点后消失（若 $u_i=v_i$，则这个人在 $t_i$ 时刻出现后立即消失）。

问最早在哪一时刻，有两人正好相遇。若不存在这样的时刻，输出 $-1$。

题解：

考虑序列上的问题。

不难发现，每个人的时间-位置图像是个一次函数，令横坐标为时刻，纵坐标为位置。我们要求若干条线段最早的交点。

这个可以使用 set + 扫描线解决。具体地，每次在一条线段的开头处插入线段，和左右两条线段判相交。在一条线段的结尾处删除线段，并把它左右两边的线段判相交。直到当前考虑的横坐标超过最早的交点的横坐标。

set 可以使用自定义比较器，以每个点当前横坐标下的纵坐标为关键字。由于在第一次相交时就退出，所以之前都保证线段的相对位置关系不变，则平衡树的结构不变，不会出现问题。

时间复杂度 $O(n\log n)$。

考虑树上的问题，不难想到树链剖分，把每个人走的路径拆成若干条链判断。

对每条重链跑一遍扫描线即可。

注意精度问题。这里求线段相交时，直接解一次函数可能会有精度问题。我们可以记录每个人的速度，然后做一个相遇/追及问题，即可提高精度。

时间复杂度 $O(n\log^2 n)$。注意各种细节。

Code：

#include<cstdio>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int N=114514;
const double eps=1e-9;
int n,m,head[N],cnt,fa[N],dep[N],son[N],sz[N],top[N];
struct edge{
    int to,nxt;
}e[N<<1];
struct point{
    double x,y;
    inline point operator-(const point&rhs)const{return(point){x-rhs.x,y-rhs.y};}
    inline bool operator<(const point&rhs)const{return x<rhs.x;}
};
vector<pair<point,point> >Vec;
vector<int>VV;
double X;
struct com{
    inline bool operator()(int a,int b)const{
        return Vec[a].first.y+(X-Vec[a].first.x)*VV[a]+eps<Vec[b].first.y+(X-Vec[b].first.x)*VV[b];
    }
};
struct DataStructure{
    vector<pair<point,point> >vec;
    vector<int>V;
    set<int,com>st;
    struct data{
        double x,y;
        int a,b;
        inline bool operator<(const data&rhs)const{return fabs(x-rhs.x)<eps?a>rhs.a:x<rhs.x;}
    };
    void insert(double t1,double t2,double x1,double x2,int c){
        vec.push_back(make_pair((point){t1,x1},(point){t2,x2}));
        if(x1>x2)c=-c;
        V.push_back(c);
    }
    inline double cross(point a,point b){
        return a.x*b.y-a.y*b.x;
    }
    inline double is_cross(int ia,int ib){
        double _1=cross(vec[ia].second-vec[ia].first,vec[ib].first-vec[ia].first);
        double _2=cross(vec[ia].second-vec[ia].first,vec[ib].second-vec[ia].first);
        if(!(_1-eps<0&&_2+eps>0||_1+eps>0&&_2-eps<0))return 0;
        _1=cross(vec[ib].second-vec[ib].first,vec[ia].first-vec[ib].first);
        _2=cross(vec[ib].second-vec[ib].first,vec[ia].second-vec[ib].first);
        if(!(_1-eps<0&&_2+eps>0||_1+eps>0&&_2-eps<0))return 0;
        return 1;
    }
    inline point get_dot(int ia,int ib){
        double s=vec[ib].first.x*V[ib]-vec[ia].first.x*V[ia]-vec[ib].first.y+vec[ia].first.y;
        if(fabs(V[ia]-V[ib])<eps){
            if(fabs(s)<=eps)return max(vec[ia].first,vec[ib].first);
            return(point){1e18,1e18};
        }
        double x=(s)/(V[ib]-V[ia]);
        return(point){x,114514};
    }
    vector<data>vc;
    void work(double&ans){
        Vec=vec,VV=V;
        for(int i=0;i<vec.size();++i)
        vc.push_back((data){vec[i].first.x,vec[i].first.y,i,-1}),
        vc.push_back((data){vec[i].second.x,vec[i].second.y,-1,i});
        sort(vc.begin(),vc.end());
        point ss=(point){1e18,1e18};
        for(int I=0;I<vc.size();++I){
            data tp=vc[I];
            if(ans-eps<tp.x)break;
            if(tp.x>ss.x-eps)break;
            X=tp.x;
            if(tp.a!=-1){
                int id=tp.a;
                auto it=st.lower_bound(tp.a);
                if(it!=st.end()){
                    if(is_cross(*it,id)){
                        point p=get_dot(*it,id);
                        ss=min(ss,p);
                    }
                }
                if(it!=st.begin()){
                    --it;
                    if(is_cross(*it,id)){
                        point p=get_dot(*it,id);
                        ss=min(ss,p);
                    }
                }
                st.insert(id);
            }else{
                int id=tp.b;
                auto qwq=st.lower_bound(id);
                st.erase(qwq);
                auto it=st.lower_bound(tp.a);
                if(it!=st.end()&&it!=st.begin()){
                    auto itt=it;--itt;
                    if(is_cross(*it,*itt)){
                        point p=get_dot(*it,*itt);
                        ss=min(ss,p);
                    }
                    if(is_cross(*it,id)){
                        point p=get_dot(*it,id);
                        ss=min(ss,p);
                    }
                    if(is_cross(id,*itt)){
                        point p=get_dot(id,*itt);
                        ss=min(ss,p);
                    }
                }
            }
        }
        st.clear();
        ans=min(ans,ss.x);
    }
}A[N];
void dfs(int now){
    sz[now]=1;
    for(int i=head[now];i;i=e[i].nxt)
    if(!dep[e[i].to]){
        dep[e[i].to]=dep[now]+1,fa[e[i].to]=now;
        dfs(e[i].to);
        sz[now]+=sz[e[i].to];
        if(!son[now]||sz[son[now]]<sz[e[i].to])son[now]=e[i].to;
    }
}
void dfs2(int now){
    if(son[now])top[son[now]]=top[now],dfs2(son[now]);
    for(int i=head[now];i;i=e[i].nxt)
    if(e[i].to!=son[now]&&dep[e[i].to]>dep[now])dfs2(top[e[i].to]=e[i].to);
}
inline int LCA(int x,int y){
    while(top[x]!=top[y])
    if(dep[top[x]]>dep[top[y]])x=fa[top[x]];else y=fa[top[y]];
    return dep[x]<dep[y]?x:y;
}
inline int dist(int x,int y,int lca=0){
    if(!lca)lca=LCA(x,y);
    return dep[x]+dep[y]-2*dep[lca];
} 
void insert(int t,int c,int x,int y){
    int lca=LCA(x,y);
    double tu=t,tv=t+1.*dist(x,y,lca)/c;
    while(top[x]!=top[y])
    if(dep[top[x]]>dep[top[y]]){
        A[top[x]].insert(tu,tu+1.*(dep[x]-dep[fa[top[x]]])/c,dep[x],dep[fa[top[x]]],c);
        tu+=1.*(dep[x]-dep[fa[top[x]]])/c;
        x=fa[top[x]];
    }else{
        A[top[y]].insert(tv-1.*(dep[y]-dep[fa[top[y]]])/c,tv,dep[fa[top[y]]],dep[y],c);
        tv-=1.*(dep[y]-dep[fa[top[y]]])/c;
        y=fa[top[y]];
    }
    A[top[x]].insert(tu,tv,dep[x],dep[y],c);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
        e[++cnt]=(edge){u,head[v]},head[v]=cnt;
    }
    dfs(dep[1]=1),dfs2(top[1]=1);
    for(int i=1;i<=m;++i){
        int t,c,u,v;
        scanf("%d%d%d%d",&t,&c,&u,&v);
        insert(t,c,u,v);
    }
    double ans=1e17;
    for(int i=1;i<=n;++i)
    if(top[i]==i)A[i].work(ans);
    if(ans>1e16)puts("-1");else printf("%.8f\n",ans);
    return 0;
}
Powered by Hexo
Theme - Material