[ABC250Ex] Trespassing Takahashi Solution

更好的阅读体验戳此进入

题面

给定一张 $n$$n$ 个点 $m$$m$ 条边的无向连通简单图。每条边存在 $a_i,b_i,c_i$$a_i, b_i, c_i$，表示 $a_i\to b_i$$a_i \rightarrow b_i$ 或 $b_i\to a_i$$b_i \rightarrow a_i$ 耗时 $c_i$$c_i$。给定 $k$$k$，定义 $n$$n$ 个点中只有前 $k$$k$ 个点有房子，$q$$q$ 次询问，每次给定 $x,y,t$$x, y, t$，求从 $x$$x$ 到 $y$$y$ 连续的不在房子中的时间是否一定会超过 $t$$t$，超过输出 No，反之输出 Yes。保证询问中 $t$$t$ 满足升序。

Solution

考虑维护对于走每条边时需要多长时间才能连通最近的两个房子，换句话说，满足这个时间的时候这条边就一定可以被走。具体维护可以考虑建一个超级源点并向所有房子连个边，然后跑个 Dijk 即可，当然直接往队列里把所有房子点都塞进去也行。然后我们可以令 $c_i\leftarrow c_i+di{s}_{a_i}+di{s}_{b_i}$$c_i \leftarrow c_i + dis_{a_i} + dis_{b_i}$ 即可，然后显然可以用并查集维护。

具体地，每次询问将边集里所有新的 $c_i$$c_i$ 满足 $c_i\le t$$c_i \le t$ 的边加上，用并查集维护，然后查询一下 $x,y$$x, y$ 是否连通即可，这个复杂度是 $O(mq)$$O(mq)$ 的，当然发现 $t$$t$ 符合升序，所以给边排个序跑一边即可，最终复杂度应该是卡在排序和 Dijk 上，也就是 $O(n\log n+m\log m)$$O(n \log n + m \log m)$。

同时不难想到即使 $t$$t$ 不符合升序也可以离线排个序再跑，复杂度多个 $O(q\log q)$$O(q \log q)$ 而已。至此本题已经结束，下面是一道加强版的双倍经验。

存在一道双倍经验 CF1253F Cheap Robot，略有区别，这里简单说一下：这道题的区别就在于询问的是最小的 $t$$t$，这样的话实际上是不太好用刚才的思路离线下来维护的，有一个复杂度不太正确但能过的思路，就是将每个询问的 $a,b$$a, b$ 分别挂在两个点上，然后将 $c_i$$c_i$ 排序，从小到大依次加边，同时更新所有挂在连通块根上的答案，再对应的把询问合上去。但是这个的并查集一定需要按秩合并，否则如果 clear() 之后 shrink_to_fit() 就会 TLE，否则会 MLE，按秩合并会保证合并询问的时候不会复制太多次以保证空间。这个东西的复杂度理论上似乎可以被卡到 $O(mq)$$O(mq)$，但是本题没卡。当然还有一个我口糊的剪枝，就是挂在点上的询问我们用链表维护，然后贪心地取第一次更新这个点时的答案，显然不劣，于是更新后 $O(1)$$O(1)$ 删除即可，但是这个东西理论上也能被卡到 $O(mq)$$O(mq)$，不过需要精细设计数据。当然正确的做法最后应该是建出最小生成树然后树剖或者倍增之类的实现。

Code

xxxxxxxxxx
96
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
struct Edge{
26
    Edge* nxt;
27
    int to;
28
    ll val;
29
    OPNEW;
30
}ed[410000];
31
ROPNEW(ed);
32
Edge* head[210000];
33

34
int N, M, K;
35
bitset < 210000 > vis;
36
ll dis[210000];
37
priority_queue < tuple < ll, int, int >, vector < tuple < ll, int, int > >, greater < tuple < ll, int, int > > > edgs;
38

39
class UnionFind{
40
private:
41
    int fa[210000];
42
public:
43
    UnionFind(void){for(int i = 1; i <= 201000; ++i)fa[i] = i;}
44
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
45
    void Union(int origin, int son){fa[Find(son)] = Find(origin);}
46
}uf;
47

48
void Dijk(void){
49
    memset(dis, 0x3f, sizeof dis);
50
    priority_queue < pair < ll, int >, vector < pair < ll, int > >, greater < pair < ll, int > > > cur;
51
    for(int i = 1; i <= K; ++i)cur.push({dis[i] = 0, i});
52
    while(!cur.empty()){
53
        int p = cur.top().second; cur.pop();
54
        if(vis[p])continue;
55
        vis[p] = true;
56
        for(auto i = head[p]; i; i = i->nxt)
57
            if(dis[p] + i->val < dis[SON])
58
                dis[SON] = dis[p] + i->val, cur.push({dis[SON], SON});
59
    }
60
}
61
int main(){
62
    N = read(), M = read(), K = read();
63
    for(int i = 1; i <= M; ++i){
64
        int s = read(), t = read(), v = read();
65
        head[s] = new Edge{head[s], t, v};
66
        head[t] = new Edge{head[t], s, v};
67
    }Dijk();
68
    for(int p = 1; p <= N; ++p)
69
        for(auto i = head[p]; i; i = i->nxt)
70
            edgs.push({i->val + dis[p] + dis[SON], p, SON});
71
    int Q = read();
72
    while(Q--){
73
        int s = read(), t = read(); ll lim = read < ll >();
74
        while(!edgs.empty() && get < 0 >(edgs.top()) <= lim)
75
            uf.Union(get < 1 >(edgs.top()), get < 2 >(edgs.top())), edgs.pop();
76
        printf("%s\n", uf.Find(s) == uf.Find(t) ? "Yes" : "No");
77
    }
78
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
79
    return 0;
80
}
81

82
template < typename T >
83
inline T read(void){
84
    T ret(0);
85
    int flag(1);
86
    char c = getchar();
87
    while(c != '-' && !isdigit(c))c = getchar();
88
    if(c == '-')flag = -1, c = getchar();
89
    while(isdigit(c)){
90
        ret *= 10;
91
        ret += int(c - '0');
92
        c = getchar();
93
    }
94
    ret *= flag;
95
    return ret;
96
}

UPD

update-2022_12_20 初稿