这个题主要是当做手写 bitset
板子来写的。
Idea:lxl Solution:lxl Std:lxl Data:lxl
对这题的评价:1/11
大概是 lxl 评价最低的题吧……
题意简述
珂朵莉给你一个无向图,每次查询的时候给一堆二元组 $(x_i,y_i)$ 。
求图中有多少个点 $u$ 与至少一个这次询问给出的二元组 $(x_i,y_i)$ 满足 $dist(u,x_i) \le y_i$ ,其中 $dist(u, v)$ 表示 $u, v$ 这两个点在图中的距离(不连通为 $\inf$),边权全为 $1$ 。
记 $n$ 为点数, $m$ 为边数, $q$ 为询问个数, $cnt$ 为给出二元组的总数。
$1\le n\le 10^3, 1\le m, q\le 10^5, cnt \le 2.1 \times 10^6$ 。
主要思路
每个点上记个 bitset
$f[i]$ , $f[i][j]$ 表示距离点 $i$ 不大于 $j$ 的点数。
可以 bfs
处理这些 bitset
,每次查询就是把一堆 bitset
或起来。
时间复杂度 $O(n\times m + \frac{n\times cnt}{\omega})$ ,空间 $O(\frac{n^3}{\omega})$ 。
参考代码
把 bitset
的大部分操作都写了一遍。
1 |
|