出题人关于 F 题的一点说明
F 题内测初期，由于其表述并不好的题意，加上这题本身题面就不简洁，导致没什么人愿意去写。同时，这题一眼给人的感觉就是模拟题，内测期间唯一的选手使用分数类模板+优先队列模拟的写法，很难写，后面貌似是直接弃了。我提出 std 做法很简洁，可以验验 std 做法，但是没有回应。最后就一直搁置到比赛了。后面题意改成现在这个基本没什么问题的版本的时候，估计大家已经被题目风评劝退了，其次是本身 F 题就不严格需要很多人都做，最后的结果这题几乎没有有效验题。最后的结果大家都知道， std 赛后有被 hack。
不过，出题人认为这个 hack 是 std 一个小细节写错了，稍微改一下就行，大方向做法没有问题。
如果还有问题，欢迎联系出题人 hack。
下面是原题解：
F
考虑各边之间独立。
所以把所有 次线路上的行车离线下来，按进入线路的时间升序处理。
扫描这 条线路，对于当前这条线路，当前车是否追尾只和当前这条边上已开过的，未产生追尾的车中最晚的一趟有关（证明下面写），所以每条边只记录最晚的一趟车。所以只要判断两车是否会追尾。
令时间为 轴，路程为
轴，速度即为斜率。
假设这两趟车 出发时间为
，到达
时间为
，则追尾当且仅当
。
时间直接算实数会有精度误差，因为速度是定值，时间等于路程除以速度，所以累计一下路程，把上述式子展开计算即可。
若当前车产生追尾，则标记它，在后续过程中忽略。
对于特殊情况，其实只要 “把所有 次线路上的行车离线下来，按进入线路的时间升序处理。” 时，对于时间相同的车，按编号为第二关键字降序即可。
时间复杂度：。
证明：
对于当前线路中，若干未产生追尾的车，显然要追尾首先追的是在最后面的。如果时间不是最晚的，那它不会是最后的。
一种可能会想复杂的特殊情况：若 车进入
后会追尾
，但是在追尾
之前，被后面更晚出发的
追上了怎么办（如果我们直接判断
产生追尾就把它忽略掉的话，就判断不了
追尾）？实际上，若出现这种情况，那么本身
还是会追尾
的，因为题目只要判断车是否存在追尾，所以等价的。
原 std 的问题是，有一种情况是，对于若干相同时间出发的列车，std 按时间顺序判断时，可能会出现编号最大的那一辆与当前最晚的车产生了追尾，那么 std 就把它去掉了，这是不合理的。所以应该先用编号大的去标记同时出发的其它列车，再去和当前最晚的车进行判断即可。
下面是修改后的 std：
#include<bits/stdc++.h>
#define For(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long i64;
const int N = 1e6 + 10;
struct train {
int x, v, k;
vector<int> a;
} a[N];
struct edge {
int u, v, w;
} p[N];
struct line {
i64 s, v;
int id1, id2;
bool operator <(const line &a) const {
if (s * a.v == a.s * v) return id2 > a.id2;
return s * a.v < a.s * v;
}
bool operator==(const line &a) const {
return s * a.v == a.s * v;
}
};
line Q[N];
bool st[N];
bool inter(line x, line y, int len) {
i64 res1, res2;
res1 = (x.s * y.v - y.s * x.v);
if (res1) res1 = res1 / abs(res1);
x.s += len, y.s += len;
res2 = (x.s * y.v - y.s * x.v);
if (res2) res2 = res2 / abs(res2);
return res1 * res2 <= 0;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
int i;
For(i, 1, m) {
cin >> a[i].x >> a[i].v >> a[i].k;
a[i].a.resize(a[i].k + 1);
int j;
For(j, 1, a[i].k) cin >> a[i].a[j];
}
int M;
cin >> M;
map<pair<int, int>, int> mp;
For(i, 1, M) {
int u, v, w;
cin >> u >> v >> w;
mp[ {u, v}] = i;
p[i] = {u, v, w};
}
vector<line> q;
For(i, 1, m) {
int j;
i64 s = a[i].x * a[i].v;
For(j, 1, a[i].k - 1) {
int id = mp[ {a[i].a[j], a[i].a[j + 1]}];
q.push_back({s, a[i].v, id, i});
s += p[id].w;
}
}
sort(q.begin(), q.end());
vector<bool> vis(m + 1);
for (unsigned i = 0; i < q.size(); i++) {
if (vis[q[i].id2]) continue;
/* 唯一的修改
for (unsigned j = i + 1; j < q.size(); j++) {
if (q[j] == q[i]) {
vis[q[j].id2] = 1;
}
else break;
}*/
if (!st[q[i].id1]) {
Q[q[i].id1] = q[i];
st[q[i].id1] = 1;
continue;
}
auto now = Q[q[i].id1];
if (inter(now, q[i], p[q[i].id1].w)) vis[q[i].id2] = 1;
else Q[q[i].id1] = q[i];
}
For(i, 1, m) if (vis[i]) cout << "YES\n"; else cout << "NO\n";
return 0;
}
