题目翻译
  • 板块CF1635E Cars
  • 楼主HyperSQ
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/8/11 10:23
  • 上次更新2023/10/27 16:00:11
查看原帖
题目翻译
134623
HyperSQ楼主2022/8/11 10:23

一维数轴上有 nn 个初始不重叠的动点,它们初始有某个固定的朝向,但可以以任意的非零速率运动。

如果某两个动点 uu vv 在运动过程中保证一定会相遇,那么这两个点的关系就称为注定相关(destined)

如果某两个动点 uu vv 在运动过程中保证一定不会相遇,那么这两个点的关系就称为不相关(irrelevant)

现在给定了 mm 对关系,要求给出一种方案(即所有动点的初始位置 xix_i、朝向 orii{L,R}ori_i\in\{L,R\})满足这些关系,或判断无解。

2n2105, 1mmin(2105,n(n1)2)2 \leq n\leq 2\cdot 10^5,\ 1\leq m \leq \min(2\cdot 10^5,\frac{n(n-1)}{2})

一维数轴上有 $n$ 个初始不重叠的动点,它们初始有某个**固定**的朝向,但可以以**任意**的非零速率运动。

如果某两个动点 $u$ $v$ 在运动过程中保证一定会相遇,那么这两个点的关系就称为**注定相关(destined)**。

如果某两个动点 $u$ $v$ 在运动过程中保证一定不会相遇,那么这两个点的关系就称为**不相关(irrelevant)**。

现在给定了 $m$ 对关系,要求给出一种方案(即所有动点的初始位置 $x_i$、朝向 $ori_i\in\{L,R\}$)满足这些关系,或判断无解。

$2 \leq n\leq 2\cdot 10^5,\ 1\leq m \leq \min(2\cdot 10^5,\frac{n(n-1)}{2})$
2022/8/11 10:23
加载中...