首页 > 其他分享 >CF704E Iron Man 题解

CF704E Iron Man 题解

时间：2024-08-17 11:37:40浏览次数：10  
标签：std Frac int 题解 top res kMaxN Iron CF704E

Description

“铁人”yyb 在玩游戏。在一个 \(n\) 个点的树上，yyb 放置了 \(m\) 个鸡贼。每个鸡贼有四个整数参数 \(t_i,c_i,v_i,u_i\)，表示这个鸡贼会在 \(t_i\) 时刻出现在点 \(v_i\)，并以每时刻 \(c_i\) 条边的速度向 \(u_i\) 点匀速移动，到达 \(u_i\) 点时立刻消失。

如果一个时刻有两个鸡贼在同一位置，它们会立刻爆炸。

（注意，如果一个鸡贼的 \(u_i=v_i\) 那么它会在 \(t_i\) 时刻出现，此时如果这个点有其它鸡贼一样会发生爆炸）

yyb 想知道最早有鸡贼爆炸的时刻。如果自始至终都没发生爆炸输出 -1。

如果你的答案和标准答案的绝对或相对误差不超过 \(10^{-6}\) 那么被视为正确。

Solution

注意到树上问题很不好做，考虑通过树剖将每组移动拆分成 \(O(\log n)\) 条链，然后转化为对于所有的 \(O(n)\) 条链判断。

那么可以对于每个链用 \(x\) 表示时间，\(y\) 表示位置，所以每组移动就可以转化为一个线段，然后需要求出这些线段的交点中 \(x\) 坐标的最小值。

考虑扫描线，把每个线段左右端点的 \(x\) 坐标作为关键点，容易发现对于一对不相交的线段一定满足他们在所有的关键点时刻的 \(y\) 坐标大小关系不变。

于是可以用 set 维护当前时刻每个线段的 \(y\) 坐标，观察之后会发现每对相交的线段一定满足在某个相交之前的时刻他们在 set 上是相邻的，所以只要每次加入一个线段时求出这个线段和它前驱、后继的答案，如果答案已经小于当前时刻就说明找到了最终答案。

注意这里 set 需要重载运算符，由于找到答案后会直接退出所以不会出现奇怪的问题。

时间复杂度：\(O(n+m\log^2n)\)。

Code

手写分数类实现 
#include <bits/stdc++.h>

#define int int64_t

using f64 = long double;

const int kMaxN = 1e5 + 5;
const f64 kEps = 1e-7;

struct Frac {
  int x, y; // x / y

  void fix() {
    if (y < 0) x = -x, y = -y;
  }

  Frac(__int128_t _x = 0, __int128_t _y = 1) {
    __int128_t d = std::__gcd(_x, _y);
    x = _x / d, y = _y / d;
    if (y < 0) x = -x, y = -y;
  }

  friend Frac operator +(Frac a, Frac b) { return Frac(a.x * b.y + a.y * b.x, a.y * b.y); }
  friend Frac operator -(Frac a, Frac b) { return Frac(a.x * b.y - a.y * b.x, a.y * b.y); }
  friend Frac operator *(Frac a, Frac b) { return Frac(a.x * b.x, a.y * b.y); }
  friend Frac operator /(Frac a, Frac b) { return Frac(a.x * b.y, a.y * b.x); }
  friend bool operator <(Frac a, Frac b) { a.fix(), b.fix(); return (__int128_t)a.x * b.y < (__int128_t)a.y * b.x; }
  friend bool operator <=(Frac a, Frac b) { a.fix(), b.fix(); return (__int128_t)a.x * b.y <= (__int128_t)a.y * b.x; }
  friend bool operator >(Frac a, Frac b) { a.fix(), b.fix(); return (__int128_t)a.x * b.y > (__int128_t)a.y * b.x; }
  friend bool operator >=(Frac a, Frac b) { a.fix(), b.fix(); return (__int128_t)a.x * b.y >= (__int128_t)a.y * b.x; }
  friend bool operator ==(Frac a, Frac b) { a.fix(), b.fix(); return (__int128_t)a.x * b.y == (__int128_t)a.y * b.x; }
  friend bool operator ==(Frac a, int b) { return a.x == (__int128_t)a.y * b; }
  friend bool operator !=(Frac a, int b) { return a.x != (__int128_t)a.y * b; }
  f64 real() { return (f64)x / y; }
};

int n, m;
int p[kMaxN], sz[kMaxN], wson[kMaxN], top[kMaxN], dep[kMaxN], dfn[kMaxN];
f64 ans = 1e18;
Frac a[kMaxN][4];
std::vector<int> G[kMaxN];
std::vector<std::pair<int, int>> upd[kMaxN * 2];
std::vector<std::tuple<Frac, Frac, Frac, Frac>> vec[kMaxN * 2];
// [初始位置，出现时间，结束时间，速度]

void dfs1(int u, int fa) {
  p[u] = fa, dep[u] = dep[fa] + 1, sz[u] = 1;
  for (auto v : G[u]) {
    if (v == fa) continue;
    dfs1(v, u);
    sz[u] += sz[v];
    if (sz[v] > sz[wson[u]]) wson[u] = v;
  }
}

void dfs2(int u, int fa, int t) {
  static int cnt = 0;
  top[u] = t;
  if (wson[u]) dfs2(wson[u], u, t);
  for (auto v : G[u]) {
    if (v == fa || v == wson[u]) continue;
    dfs2(v, u, v);
  }
}

void prework() {
  dfs1(1, 0), dfs2(1, 0, 1);
}

void work(int t, int c, int u, int v) {
  std::vector<std::tuple<int, int, int>> vecu, vecv;
  for (; top[u] != top[v];) {
    if (dep[top[u]] >= dep[top[v]]) {
      vecu.emplace_back(top[u], dep[u] - dep[top[u]], 0);
      vecu.emplace_back(top[u] + n, 1, 0);
      u = p[top[u]];
    } else {
      vecv.emplace_back(top[v], 0, dep[v] - dep[top[v]]);
      vecv.emplace_back(top[v] + n, 0, 1);
      v = p[top[v]];
    }
  }
  if (dep[u] <= dep[v])
    vecv.emplace_back(top[u], dep[u] - dep[top[u]], dep[v] - dep[top[u]]);
  else
    vecu.emplace_back(top[u], dep[u] - dep[top[u]], dep[v] - dep[top[u]]);

  std::reverse(vecv.begin(), vecv.end());
  for (auto p : vecv) vecu.emplace_back(p);
  Frac now = Frac(t, 1);
  for (auto [id, l, r] : vecu) {
    vec[id].emplace_back(Frac(l, 1), now, now + Frac(abs(l - r), c), Frac(l <= r ? c : -c, 1));
    now = now + Frac(abs(l - r), c);
  }
}

int getid(std::vector<Frac> &vec, Frac x) {
  int L = -1, R = vec.size(), res = -1;
  while (L + 1 < R) {
    int mid = (L + R) >> 1;
    if (x <= vec[mid]) R = res = mid;
    else L = mid;
  }
  return res;
}

Frac calc(int x, int y) {
  Frac s = a[x][3] * a[x][1] - a[y][3] * a[y][1] + a[y][0] - a[x][0];
  Frac v = a[x][3] - a[y][3];
  if (v == 0 && !(s == 0)) {
    return Frac(1e14, 1);
  } else if (v == 0) {
    if (std::max(a[x][1], a[y][1]) <= std::min(a[x][2], a[y][2])) return std::max(a[x][1], a[y][1]);
    else return Frac(1e14, 1);
  } else {
    Frac t = s / v;
    if (t >= a[x][1] && t >= a[y][1] && t <= a[x][2] && t <= a[y][2]) return t;
    else return Frac(1e14, 1);
  }
}

void solve(int x) {
  std::vector<Frac> tmp, unq;
  int tot = 0;
  Frac nowt = Frac(0, 1);
  auto cmp = [&] (int i, int j) -> bool {
    return a[i][0] + a[i][3] * (nowt - a[i][1]) < a[j][0] + a[j][3] * (nowt - a[j][1]);
  };
  for (auto [p, l, r, c] : vec[x]) {
    ++tot;
    a[tot][0] = p, a[tot][1] = l, a[tot][2] = r, a[tot][3] = c;
    tmp.emplace_back(l), tmp.emplace_back(r);
  }
  std::sort(tmp.begin(), tmp.end());
  for (int i = 0; i < (int)tmp.size(); ++i) {
    if (!i) unq.emplace_back(tmp[i]);
    else if (!(tmp[i] == tmp[i - 1])) unq.emplace_back(tmp[i]);
  }
  for (int i = 0; i < (int)unq.size(); ++i) upd[i].clear();
  for (int i = 1; i <= tot; ++i) {
    upd[getid(unq, a[i][1])].emplace_back(i, 1);
    upd[getid(unq, a[i][2])].emplace_back(i, -1);
  }
  std::set<int, decltype(cmp)> st(cmp);
  Frac res = Frac(1e12, 1);
  for (int i = 0; i < (int)unq.size(); ++i) {
    nowt = unq[i];
    if (res < nowt) break;
    for (auto [x, v] : upd[i]) {
      if (v == 1) {
        auto it = st.lower_bound(x);
        if (it != st.end()) {
          Frac val = calc(*it, x);
          res = std::min(res, val);
          if (res < nowt) return void(ans = std::min(ans, res.real()));
        }
        if (it != st.begin()) {
          --it;
          Frac val = calc(*it, x);
          res = std::min(res, val);
          if (res < nowt) return void(ans = std::min(ans, res.real()));
        }
        st.emplace(x);
      }
    }
    for (auto [x, v] : upd[i]) {
      if (v == -1) st.erase(x);
    }
  }
  ans = std::min(ans, res.real());
}

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i < n; ++i) {
    int u, v;
    std::cin >> u >> v;
    G[u].emplace_back(v), G[v].emplace_back(u);
  }
  prework();
  for (int i = 1; i <= m; ++i) {
    int t, c, u, v;
    std::cin >> t >> c >> u >> v;
    work(t, c, u, v);
  }
  for (int i = 1; i <= 2 * n; ++i) solve(i);
  if (ans >= 1e10) std::cout << "-1\n";
  else std::cout << std::fixed << std::setprecision(10) << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}
float128 实现 
#include <bits/stdc++.h>

// #define int int64_t

using f64 = long double;
using f128 = __float128;

const int kMaxN = 1e5 + 5;
const f128 kEps = 1e-7;

int n, m;
int p[kMaxN], sz[kMaxN], wson[kMaxN], top[kMaxN], dep[kMaxN], dfn[kMaxN];
f128 ans = 1e18, a[kMaxN][4];
std::vector<int> G[kMaxN];
std::vector<std::pair<int, int>> upd[kMaxN * 2];
std::vector<std::tuple<f128, f128, f128, f128>> vec[kMaxN * 2];
// [初始位置，出现时间，结束时间，速度]

void dfs1(int u, int fa) {
  p[u] = fa, dep[u] = dep[fa] + 1, sz[u] = 1;
  for (auto v : G[u]) {
    if (v == fa) continue;
    dfs1(v, u);
    sz[u] += sz[v];
    if (sz[v] > sz[wson[u]]) wson[u] = v;
  }
}

void dfs2(int u, int fa, int t) {
  static int cnt = 0;
  top[u] = t, dfn[u] = ++cnt;
  if (wson[u]) dfs2(wson[u], u, t);
  for (auto v : G[u]) {
    if (v == fa || v == wson[u]) continue;
    dfs2(v, u, v);
  }
}

void prework() {
  dfs1(1, 0), dfs2(1, 0, 1);
}

void work(int t, int c, int u, int v) {
  std::vector<std::tuple<int, int, int>> vecu, vecv;
  for (; top[u] != top[v];) {
    if (dep[top[u]] >= dep[top[v]]) {
      vecu.emplace_back(top[u], dep[u] - dep[top[u]], 0);
      vecu.emplace_back(top[u] + n, 1, 0);
      u = p[top[u]];
    } else {
      vecv.emplace_back(top[v], 0, dep[v] - dep[top[v]]);
      vecv.emplace_back(top[v] + n, 0, 1);
      v = p[top[v]];
    }
  }
  if (dep[u] <= dep[v])
    vecv.emplace_back(top[u], dep[u] - dep[top[u]], dep[v] - dep[top[u]]);
  else
    vecu.emplace_back(top[u], dep[u] - dep[top[u]], dep[v] - dep[top[u]]);

  std::reverse(vecv.begin(), vecv.end());
  for (auto p : vecv) vecu.emplace_back(p);
  f128 now = t;
  for (auto [id, l, r] : vecu) {
    vec[id].emplace_back(l, now, now + fabs(l - r) / c, l <= r ? c : -c);
    now += fabs(l - r) / c;
  }
}

int getid(std::vector<f128> &vec, f128 x) {
  int L = -1, R = vec.size(), res = -1;
  while (L + 1 < R) {
    int mid = (L + R) >> 1;
    if (x <= vec[mid] + kEps) R = res = mid;
    else L = mid;
  }
  return res;
}

f128 calc(int x, int y) {
  f128 s = a[x][3] * a[x][1] - a[y][3] * a[y][1] + a[y][0] - a[x][0];
  f128 v = a[x][3] - a[y][3];
  if (fabs(v) <= kEps && fabs(s) > kEps) return 1e18;
  else if (fabs(v) <= kEps) {
    if (std::max(a[x][1], a[y][1]) <= std::min(a[x][2], a[y][2]) + kEps) return std::max(a[x][1], a[y][1]);
    else return 1e18;
  } else {
    f128 t = s / v;
    if (t >= a[x][1] - kEps && t >= a[y][1] - kEps && t <= a[x][2] + kEps && t <= a[y][2] + kEps) return t;
    else return 1e18;
  }
}

void solve(int x) {
  static std::vector<f128> tmp, unq;
  tmp.clear(), tmp.shrink_to_fit();
  unq.clear(), unq.shrink_to_fit();
  int tot = 0;
  f128 nowt = 0;
  auto cmp = [&] (int i, int j) -> bool {
    return a[i][0] + a[i][3] * (nowt - a[i][1]) < a[j][0] + a[j][3] * (nowt - a[j][1]);
  };
  for (auto [p, l, r, c] : vec[x]) {
    ++tot;
    a[tot][0] = p, a[tot][1] = l, a[tot][2] = r, a[tot][3] = c;
    tmp.emplace_back(l), tmp.emplace_back(r);
  }
  std::sort(tmp.begin(), tmp.end());
  for (int i = 0; i < (int)tmp.size(); ++i) {
    if (!i) unq.emplace_back(tmp[i]);
    else if (fabs(tmp[i] - tmp[i - 1]) > kEps) unq.emplace_back(tmp[i]);
  }
  for (int i = 0; i < (int)unq.size(); ++i) upd[i].clear();
  for (int i = 1; i <= tot; ++i) {
    upd[getid(unq, a[i][1])].emplace_back(i, 1);
    upd[getid(unq, a[i][2])].emplace_back(i, -1);
  }
  std::set<int, decltype(cmp)> st(cmp);
  f128 res = 1e18;
  for (int i = 0; i < (int)unq.size(); ++i) {
    nowt = unq[i];
    if (res < nowt - kEps) break;
    for (auto [x, v] : upd[i]) {
      if (v == 1) {
        auto it = st.lower_bound(x);
        if (it != st.end()) {
          f128 val = calc(*it, x);
          res = std::min(res, val);
          if (res < nowt - kEps) return void(ans = std::min(ans, res));
        }
        if (it != st.begin()) {
          --it;
          f128 val = calc(*it, x);
          res = std::min(res, val);
          if (res < nowt - kEps) return void(ans = std::min(ans, res));
        }
        st.emplace(x);
      }
    }
    for (auto [x, v] : upd[i]) {
      if (v == -1) st.erase(x);
    }
  }
  ans = std::min(ans, res);
}

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i < n; ++i) {
    int u, v;
    std::cin >> u >> v;
    G[u].emplace_back(v), G[v].emplace_back(u);
  }
  prework();
  for (int i = 1; i <= m; ++i) {
    int t, c, u, v;
    std::cin >> t >> c >> u >> v;
    work(t, c, u, v);
  }
  for (int i = 1; i <= 2 * n; ++i) solve(i);
  if (ans >= 1e10) std::cout << "-1\n";
  else std::cout << std::fixed << std::setprecision(10) << (f64)ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

标签：std,Frac,int,题解,top,res,kMaxN,Iron,CF704E
From： https://www.cnblogs.com/Scarab/p/18364180

相关文章

  • 【题解】「NOIP2012」疫情控制
    https://www.luogu.com.cn/problem/P1084这道题难在贪心的思路，实现比较简单可以直接看代码。首先二分。现在转化为判定问题。可以用倍增求出每个军队最上面能到哪。结论1：我们一定不会把在除了根节点以外的军队往下移动。否则肯定不优。所以我们把能走到根节点的先存在一起......
  • [题解] [HNOI2016] 序列
    原题链接题面给定长度为$n$的序列：$a_1,a_2,\cdots,a_n$，记为\(a[1\colonn]\)。类似地，\(a[l\colonr]\)（$1\leql\leqr\leqN$）是指序列：$a_{l},a_{l+1},\cdots,a_{r-1},a_r$。若\(1\leql\leqs\leqt\leqr\leqn\)，则称$a[s\colont]$是$a[......
  • 2024杭电多校第十场 1002树上询问(题解)
    题意给一棵树，每个节点有一个权值，并且权值是一个排列。接下来有多次操作，每次操作要么是交换两个节点权值，要么是询问一个权值区间\([L,R]\)，判断是否存在树上的一个路径，使得路径上的权值恰好都在这个区间里分析由于询问的是树上的一个路径，联想到了树上莫队中对路径的处理。这里......
  • 洛谷p1717题解
    题目描述话说发源于小朋友精心设计的游戏被电脑组的童鞋们藐杀之后非常不爽，为了表示安慰和鼓励，VIP999决定请他吃一次“年年大丰收”，为了表示诚意，他还决定亲自去钓鱼。但是，因为还要准备NOIP2013,z老师只给了他 H 个小时的空余时间，假设有 n 个鱼塘都在一条水平路边，从左......
  • 洛谷p2580题解
    题目背景XS中学化学竞赛组教练是一个酷爱炉石的人。他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次，然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉（详情请见已结束比赛CON900）。题目描述这之后校长任命你为特派探员，每天记录他的点名。校长会提供化学竞......
  • 计算1~n的和题解（Mars OJ P1016）
    在这儿问一下，有人用MarsOJ的吗？有的话，评论区里回复一下，谢谢。好了切入正题题目：说明给出正整数n(1<=n<=10⁶)，计算1到n的和输入格式一行一个正整数(1<=n<=10⁶)输出格式一行一个整数，表示1到n的和样例 输入数据13输出数据16这题考的时循环，把1~n跑......
  • P4271 [USACO18FEB] New Barns P 题解
    题目传送门前置知识树的直径|最近公共祖先|并查集解法一个显而易见的结论：设点集\(A\)的直径的两个端点为\(u_{1},v_{1}\)，另一个点集\(B\)的直径的两个端点为\(u_{2},v_{2}\)，则\(A\bigcupB\)的直径端点一定是\(\{u_{1},v_{1},u_{2},v_{2}\}\)中的两个。还有......
  • P8734 奇偶覆盖 题解
    Statement矩形面积并，但是覆盖奇数次、覆盖偶数次的面积要分别输出。Solution提供一种不费脑子的做法：首先离散化、扫描线，问题变成维护区间+1-1、询问全局有多少正数是奇数、多少正数是偶数。若去除“正数”的条件，这是很容易用一个标记下传的线段树维护的，区间分别维护0,1个......
  • Git 命令大全：详细讲解与常见问题解决方案
    目录1.Git基础命令2.分支管理命令3.远程仓库管理命令4.标签管理命令5.其他常用命令6.总结Git是目前最流行的分布式版本控制系统，它使得团队协作和代码管理变得更加高效。本文将详细介绍Git的常用命令及其应用场景，并针对可能遇到的问题提供解决方案。1.Git......
  • P8518 [IOI2021] 分糖果 题解
    DescriptionKhong阿姨正在给附近一所学校的学生准备\(n\)盒糖果。盒子的编号分别为\(0\)到\(n-1\)，开始时盒子都为空。第\(i\)个盒子\((0\leqi\leqn-1)\)至多可以容纳\(c[i]\)块糖果（容量为\(c[i]\)）。Khong阿姨花了\(q\)天时间准备糖果盒。在第\(j\)天......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99