出题人关于 F 题的一点说明

F 题内测初期，由于其表述并不好的题意，加上这题本身题面就不简洁，导致没什么人愿意去写。同时，这题一眼给人的感觉就是模拟题，内测期间唯一的选手使用分数类模板+优先队列模拟的写法，很难写，后面貌似是直接弃了。我提出 std 做法很简洁，可以验验 std 做法，但是没有回应。最后就一直搁置到比赛了。后面题意改成现在这个基本没什么问题的版本的时候，估计大家已经被题目风评劝退了，其次是本身 F 题就不严格需要很多人都做，最后的结果这题几乎没有有效验题。最后的结果大家都知道， std 赛后有被 hack。

不过，出题人认为这个 hack 是 std 一个小细节写错了，稍微改一下就行，大方向做法没有问题。

如果还有问题，欢迎联系出题人 hack。

下面是原题解：

F

考虑各边之间独立。

所以把所有 $\sum(k-1)$ 次线路上的行车离线下来，按进入线路的时间升序处理。

扫描这 $\sum(k-1)$ 条线路，对于当前这条线路，当前车是否追尾只和当前这条边上已开过的，未产生追尾的车中最晚的一趟有关（证明下面写），所以每条边只记录最晚的一趟车。所以只要判断两车是否会追尾。

令时间为 $x$ 轴，路程为 $y$ 轴，速度即为斜率。

假设这两趟车 $u$ 出发时间为 $t_1,t_2$ ，到达 $v$ 时间为 $t_3,t_4$ ，则追尾当且仅当 $(t_1-t_2)\times(t_3-t_4)\le 0$ 。

时间直接算实数会有精度误差，因为速度是定值，时间等于路程除以速度，所以累计一下路程，把上述式子展开计算即可。

若当前车产生追尾，则标记它，在后续过程中忽略。

对于特殊情况，其实只要 “把所有 $\sum(k-1)$ 次线路上的行车离线下来，按进入线路的时间升序处理。” 时，对于时间相同的车，按编号为第二关键字降序即可。

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

证明：

对于当前线路中，若干未产生追尾的车，显然要追尾首先追的是在最后面的。如果时间不是最晚的，那它不会是最后的。

一种可能会想复杂的特殊情况：若 $A$ 车进入 $(u,v)$ 后会追尾 $B$ ，但是在追尾 $B$ 之前，被后面更晚出发的 $C$ 追上了怎么办（如果我们直接判断 $A$ 产生追尾就把它忽略掉的话，就判断不了 $A,C$ 追尾）？实际上，若出现这种情况，那么本身 $C$ 还是会追尾 $B$ 的，因为题目只要判断车是否存在追尾，所以等价的。

原 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) {
            if (id1 == a.id1)
                return id2 > a.id2;
            return id1 < a.id1;
        }
        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;
}