题解 - Iron Man

Macesuted QWQ LV 8 SU @ 2022-3-22 7:37:45

Statement

给出一个 $n$ 个点的树。现在有 $m$ 个人，每个人在 $t_i$ 时刻出现在树上，以每秒 $c_i$ 条边的速度从 $u_i$ 走到 $v_i$ 。请你求出最早的有两人相遇的时间，没有则输出 $-1$ 。

$1 \le n,m \le 10^5,~0 \le t_i \le 10^4$

Solution

考虑树为一条链时怎么做。发现若以时间为横坐标，每个人所处的在链上的位置为纵坐标，每个人可以被表示为一条线段，问题即为求线段交点横坐标最小值。在横坐标上做扫描线，维护一个 set 存放当前时刻所有出现的线段即可。相交线段在相交前一定相邻，每次插入删除时对相邻两线段求交点并于答案取较小值即可。关于 set 如何按照当前横坐标上每条线段对应的纵坐标排序，重载小于号令其按照当前时刻线段横坐标大小排序即可。虽然随扫描线推移过程原来为小于关系的两条线段不一定一直小于，但是这样打乱相对顺序的情况表示其已经出现了交点，不需要继续向后做扫描线了。因此直接按照当前时刻横坐标来比对是正确的。

至于树上情况应该怎么做，在树上进行树链剖分后，将每一个人的行动轨迹拆分到每条路径上的轻重链上即可。最终对每条轻重链执行上述操作，将所得的每条链的答案取最小值即可得到答案。

Code

View on GitHub

Code

/**
 * @file 704E.cpp
 * @author Macesuted (i@macesuted.moe)
 * @date 2022-03-20
 *
 * @copyright Copyright (c) 2022
 * @brief
 *      My Tutorial: https://macesuted.moe/article/cf704e
 *
 */

#include <bits/stdc++.h>
using namespace std;

namespace IO {
const int SIZE = 1 << 20;
char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1, stack[32];
char isspace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r'; }
void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); }
void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); }
char buftop(void) { return Ir == Il ? fill(), *Il : *Il; }
char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; }
void putch(char x) { return *Ol++ = x, Ol == Or ? flush() : void(); }
template <typename T>
T read(void) {
    T x = 0, f = +1;
    char c = getch();
    while (c < '0' || c > '9') c == '-' ? void(f = -f) : void(), c = getch();
    while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch();
    return x * f;
}
template <typename T>
void write(T x) {
    if (!x) putch('0');
    if (x < 0) putch('-'), x = -x;
    int top = 0;
    while (x) stack[top++] = (x % 10) ^ 48, x /= 10;
    while (top) putch(stack[--top]);
    return;
}
string getstr(const string& suf = "") {
    string s = suf;
    while (isspace(buftop())) getch();
    while (Il != Ir) {
        char* p = Il;
        while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++;
        s.append(p, Il);
        if (Il < Ir) break;
        fill();
    }
    return s;
}
void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (int i = begin; i < end; i++) putch(str[i]);
    return;
}
struct Flusher_ {
    ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace IO
using IO::getch;
using IO::getstr;
using IO::putch;
using IO::putstr;
using IO::read;
using IO::write;

bool mem1;

#define maxn 100005
#define eps 1e-10

typedef pair<int, int> pii;
typedef tuple<int, long double, int, long double> tidid;

long double TIM, ans = numeric_limits<long double>::max();

struct comp {
    long double getPos(const tidid& a) const {
        return get<1>(a) == get<3>(a) ? get<0>(a)
                                      : get<0>(a) + (TIM - get<1>(a)) * (get<2>(a) - get<0>(a)) / (get<3>(a) - get<1>(a));
    }
    bool operator()(const tidid& a, const tidid& b) const { return getPos(a) < getPos(b); }
};

vector<vector<int>> graph;
int fa[maxn], siz[maxn], son[maxn], top[maxn], dep[maxn];
vector<tidid> heav[maxn], ligh[maxn];

void dfs1(int p) {
    siz[p] = 1;
    for (auto i : graph[p])
        if (i != fa[p]) {
            fa[i] = p, dep[i] = dep[p] + 1, dfs1(i), siz[p] += siz[i];
            if (!son[p] || siz[i] > siz[son[p]]) son[p] = i;
        }
    return;
}
void dfs2(int p, int top_) {
    top[p] = top_;
    if (son[p]) dfs2(son[p], top_);
    for (auto i : graph[p])
        if (i != fa[p] && i != son[p]) dfs2(i, i);
    return;
}
int LCA(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}
void calcCross(tidid a, tidid b) {
    long double ak = (get<2>(a) - get<0>(a)) / (get<3>(a) - get<1>(a)), bk = (get<2>(b) - get<0>(b)) / (get<3>(b) - get<1>(b)),
                ad = get<0>(a) - get<1>(a) * ak, bd = get<0>(b) - get<1>(b) * bk;
    if ((ad < bd) != (ad + ak * TIM < bd + bk * TIM)) return;
    long double ret = (ad - bd) / (bk - ak);
    if (ret < max(get<1>(a), get<1>(b)) - eps || ret > min(get<3>(a), get<3>(b)) + eps) return;
    return ans = min(ans, ret), void();
}
void calc(vector<tidid>& a) {
    static vector<long double> pos;
    static vector<vector<tidid>> in, out;
    pos.clear(), pos.reserve(2 * a.size()), in.clear(), out.clear();
    for (auto i : a) pos.push_back(get<1>(i)), pos.push_back(get<3>(i));
    sort(pos.begin(), pos.end()), pos.resize(unique(pos.begin(), pos.end()) - pos.begin());
    in.resize(pos.size()), out.resize(pos.size());
    for (auto i : a)
        in[lower_bound(pos.begin(), pos.end(), get<1>(i)) - pos.begin()].push_back(i),
            out[lower_bound(pos.begin(), pos.end(), get<3>(i)) - pos.begin()].push_back(i);
    static set<tidid, comp> S1;
    S1.clear();
    for (int i = 0; i < (int)pos.size(); i++) {
        TIM = pos[i];
        if (TIM > ans) return;
        for (auto j : in[i]) {
            auto ret = S1.emplace(j);
            if (!ret.second) return ans = min(ans, pos[i]), void();
            auto pl = ret.first, pr = pl;
            if (pl != S1.begin()) calcCross(*--pl, j);
            if (++pr != S1.end()) calcCross(j, *pr);
        }
        for (auto j : out[i]) {
            auto p2 = S1.erase(S1.find(j)), p1 = p2;
            if (p1 != S1.begin() && p2 != S1.end()) calcCross(*--p1, *p2);
        }
    }
    return;
}

void solve(void) {
    int n = read<int>(), m = read<int>();
    graph.resize(n + 1);
    for (int i = 1; i < n; i++) {
        int x = read<int>(), y = read<int>();
        graph[x].push_back(y), graph[y].push_back(x);
    }
    dfs1(1), dfs2(1, 1);
    for (int i = 1; i <= m; i++) {
        long double tim = read<int>(), c = read<int>();
        int x = read<int>(), y = read<int>(), t = LCA(x, y);
        while (top[x] != top[t]) {
            heav[top[x]].emplace_back(x, tim, top[x], tim + (dep[x] - dep[top[x]]) / c), tim += (dep[x] - dep[top[x]]) / c,
                x = top[x];
            ligh[x].emplace_back(x, tim, fa[x], tim + 1 / c), tim += 1 / c, x = fa[x];
        }
        static stack<pii> cache;
        while (!cache.empty()) cache.pop();
        while (top[y] != top[t]) cache.emplace(y, top[y]), y = fa[top[y]];
        heav[top[y]].emplace_back(x, tim, y, tim + abs(dep[x] - dep[y]) / c), tim += abs(dep[x] - dep[y]) / c;
        while (!cache.empty()) {
            pii p = cache.top();
            cache.pop();
            ligh[p.second].emplace_back(fa[p.second], tim, p.second, tim + 1 / c), tim += 1 / c;
            heav[p.second].emplace_back(p.second, tim, p.first, tim + (dep[p.first] - dep[p.second]) / c),
                tim += (dep[p.first] - dep[p.second]) / c;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (auto& j : heav[i]) get<0>(j) = dep[get<0>(j)] - dep[i] + 1, get<2>(j) = dep[get<2>(j)] - dep[i] + 1;
        for (auto& j : ligh[i]) get<0>(j) = dep[get<0>(j)] - dep[i] + 2, get<2>(j) = dep[get<2>(j)] - dep[i] + 2;
        calc(heav[i]), calc(ligh[i]);
    }
    if (ans == numeric_limits<long double>::max()) return putstr("-1\n");
    cout << setiosflags(ios::fixed) << setprecision(30) << ans << endl;
    return;
}

bool mem2;

int main() {
    ios::sync_with_stdio(false);
#ifdef MACESUTED
    cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif

    int _ = 1;
    while (_--) solve();

#ifdef MACESUTED
    cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
#endif
    return 0;
}

liujiameng LV 10 @ 2023-7-26 20:27:48

链的情况

首先考虑链的情况。

建立平面直角坐标系，横轴为时间，纵轴为深度，那么链上人的运动在坐标系中是一条线段。问题转化为这些线段的第一次相交时间。

考虑扫描线。从左到右按时间先后扫描，同时维护一个线段集合，按照纵坐标深度排序。那么容易知道线段相交一定出现在集合中的相邻两个。

时间复杂度 $\Theta(n\log n)$ ，其中 $n$ 为链长度。

树的情况

解决了链的情况，容易想到树链剖分。每个人都分成 $\Theta(\log n)$ 的链，由于相撞只能发生在同一条链上，所以我们只需要处理每条链即可。时间复杂度 $\Theta(n+m\log n\log m)$ 。

实现细节：涉及精度问题，要使用 long double，如果还无法通过此题，就使用分数存储；计算线段交点时要注意处理两条线段平行的情况。

// 2023.07.26

#include<bits/stdc++.h>
using namespace std;

struct Frac{
    long long x,y;
    Frac(long long a=0,long long b=1):x(a),y(b){
        long long gcd=__gcd(abs(x),abs(y));
        if(y<0)gcd=-gcd; x/=gcd,y/=gcd;
    }
    Frac operator+(Frac tmp)const{
        return Frac(x*tmp.y+y*tmp.x,y*tmp.y);
    }
    Frac operator-(Frac tmp)const{
        return Frac(x*tmp.y-y*tmp.x,y*tmp.y);
    }
    Frac operator*(Frac tmp)const{
        return Frac(x*tmp.x,y*tmp.y);
    }
    Frac operator/(Frac tmp)const{
        return Frac(x*tmp.y,y*tmp.x);
    }
    bool operator<(Frac tmp)const{
        return x*tmp.y<y*tmp.x;
    }
    bool operator<=(Frac tmp)const{
        return x*tmp.y<=y*tmp.x;
    }
    bool operator>=(Frac tmp)const{
        return x*tmp.y>=y*tmp.x;
    }
    bool operator==(Frac tmp)const{
        return x*tmp.y==y*tmp.x;
    }
    bool operator!=(Frac tmp)const{
        return x*tmp.y!=y*tmp.x;
    }
};

int n,m; Frac answer=Frac(1e14);

struct Edge{
    int to,nxt;
}edge[500001];
int cntEdge,head[200001];
void addEdge(int u,int v){
    edge[++cntEdge]={v,head[u]},head[u]=cntEdge;
}

int fa[200001],siz[200001],dep[200001],heavy[200001];
void init(int id){
    siz[id]=1;
    for(int i=head[id];i;i=edge[i].nxt){
        if(edge[i].to==fa[id])continue;
        fa[edge[i].to]=id;
        dep[edge[i].to]=dep[id]+1;
        init(edge[i].to);
        if(siz[edge[i].to]>siz[heavy[id]])
            heavy[id]=edge[i].to;
        siz[id]+=siz[edge[i].to];
    }
}

int cntdfn,dfn[200001],rnk[200001];
int top[200001];
void decomposition(int id,int x){
    // x 为当前链顶端
    top[id]=x,dfn[id]=++cntdfn,rnk[cntdfn]=id;
    if(!heavy[id])return;
    decomposition(heavy[id],x);
    for(int i=head[id];i;i=edge[i].nxt)
        if(edge[i].to!=heavy[id]&&edge[i].to!=fa[id])
            decomposition(edge[i].to,edge[i].to);
}

int getlca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}

Frac now;

struct LineSegment{
    Frac k,b,l,r; // 线段 y = kx + b，左右端点横坐标为 l 和 r
    bool operator<(LineSegment tmp)const{
        if(k*now+b!=tmp.k*now+tmp.b)
            return k*now+b<tmp.k*now+tmp.b;
        if(l!=tmp.l)return l<tmp.l;
        if(r!=tmp.r)return r<tmp.r;
        return k<tmp.k;
    }
};
bool operator<(pair<LineSegment,int> x,pair<LineSegment,int> y){
    Frac xt=x.second?x.first.l:x.first.r,
         yt=y.second?y.first.l:y.first.r;
    if(xt==yt)return x.second>y.second;
    else return xt<yt;
}
vector<LineSegment> lines[200001];

Frac calc(LineSegment x,LineSegment y){
    if(x.k==y.k&&x.b==y.b)return max(x.l,y.l);
    if(x.k==y.k)return Frac(1e14);
    Frac res=(x.b-y.b)/(y.k-x.k);
    if(max(x.l,y.l)<=res&&res<=min(x.r,y.r))return res;
    else return Frac(1e14);
}

void solve(vector<LineSegment> r){
    multiset<LineSegment> S;
    vector<pair<LineSegment,int> > Q;
    for(LineSegment i :r)
        Q.push_back({i,1}),Q.push_back({i,0});
    sort(Q.begin(),Q.end());
    for(pair<LineSegment,int> i :Q){
        now=i.second?i.first.l:i.first.r;
        if(now>=answer)break;
        if(i.second){
            auto tmp=S.insert(i.first),tmp1=tmp,tmp2=tmp;
            if(tmp1!=S.begin())answer=min(answer,calc(*--tmp1,*tmp));
            if(++tmp2!=S.end())answer=min(answer,calc(*tmp,*tmp2));
        }
        else{
            auto tmp=S.lower_bound(i.first),tmp1=tmp,tmp2=tmp;
            if(tmp1!=S.begin()&&++tmp2!=S.end())
                answer=min(answer,calc(*--tmp1,*tmp2));
            S.erase(tmp);
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addEdge(u,v);
        addEdge(v,u);
    }
    init(1); decomposition(1,1);

    for(int i=1;i<=m;i++){
        int x,y; Frac v,s,e;
        scanf("%lld%lld%d%d",&s.x,&v.x,&x,&y);
        e=Frac(dep[x]+dep[y]-dep[getlca(x,y)]*2)/v+s;
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]]){
                int from=y,to=fa[top[y]];
                lines[top[y]].push_back({v,Frac(dep[from])-v*e,
                    e-Frac(dep[from]-dep[to])/v,e});
                e=e-Frac(dep[from]-dep[to])/v;
                y=fa[top[y]];
            }
            else{
                int from=x,to=fa[top[x]];
                lines[top[x]].push_back({Frac(0)-v,Frac(dep[from])+v*s,
                    s,s+Frac(dep[from]-dep[to])/v});
                s=s+Frac(dep[from]-dep[to])/v;
                x=fa[top[x]];
            }
        }
        if(dep[x]>dep[y])lines[top[x]].push_back({Frac(0)-v,Frac(dep[x])+v*s,s,e});
        else lines[top[x]].push_back({v,Frac(dep[y])-v*e,s,e});
    }
    for(int i=1;i<=n;i++)solve(lines[i]);
    if(answer==Frac(1e14))return printf("-1\n"),0;
    printf("%.10Lf\n",(long double)answer.x/answer.y);
    return 0;
}

ID

4107

时间

5000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

Hydro

2 条题解

Statement

Solution

Code

链的情况

树的情况

Iron Man

信息

状态

开发

支持

2 条题解

Statement

Solution

Code

链的情况

树的情况

Iron Man

信息

状态

开发

支持

还没有账户？

登录