18th CCPC浙江省赛 D. Shortest Path Query

题意

image-20211028094841263

思路

首先,题目给定了每一条边$(u,v)$都满足二进制下表示下,$u_{(2)}$是$v_{(2)}$的一个前缀,如$u=10_{2}$,$v=101_{2}$。

由此,我们考虑构建完全二叉树这样的一个结构,则在以点$u$为根节点的子树里的任意一点$v$,均满足题目所给的前缀的条件。

为了更快的求出某点是否为子树中的一点,我们预处理一下每个点的父亲fa[now][0/1/.../20]

数组第二维分别代表每个点的第$0,1,\dots,20$​个祖先(第$0$​​个祖先为它本身)。

而且,此处为完全二叉树,往上的祖先不会超过$20$个(实际上$17$个就好了,因为$2^{17}=131072>100000$,$20$​​个只是凑个整)。

最后,我们预处理每个点的深度dep[now],可以得到:

当且仅当(nxt >= now) AND (fa[nxt][dep[nxt] - dep[now]] == now)时,满足nxtnow的子树中的一个节点。

预处理时间复杂度$O(nlogn)$​​。

然后,如果$u,v$两点是可达的,那么从任一点出发,都至少能够到达它们中的某一个公共祖先

因此,在每一次询问中,我们可以考虑先找到他们的最近公共祖先。由于我们预处理了父亲数组fa[now][20],因此可以写倍增来求$LCA$。不过对于完全二叉树,我们还可以求他们二进制中的最长公共前缀,即为对应的$LCA$。

如:$u=15=1111_{(2)}, v = 12 =1100_{(2)}, LCA(u, v)=11_{(2)}=3$

image-20211028105736772

后面发现写这种还不如写倍增LCA,太蠢了,不过如果用Trie树应该就很方便了吧…

然后我们研究一下,如何求出公共祖先到$u,v$中某一点的距离。

最初的时候,写了一个优雅(但是错的一塌糊涂,甚至套了二分试图降低复杂度)的$DP$:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int search(int u, int v){
auto nxt = lower_bound(G[u].begin(), G[u].end(), (Node){v, 0LL});
return ((nxt == G[u].end() || (*nxt).v != v) ? INF : (*nxt).w);
}
void init(int pos){
int now = pos, level = 0;
dis[now][0] = 0; now >>= 1;
while(now)
{
int mindis = INF;
for(int r = pos, d = 0; r > now; r >>= 1, d++){
if(~dis[pos][d])
mindis = min(mindis, dis[pos][d] + search(r, now));
}
dis[pos][++level] = (mindis == INF ? -1 : mindis);
now >>= 1;
}
}

这段代码的实现的是求dis[pos][level]的值,dis[pos][0]=0dis[pos][1]为到达点$pos$的父亲的距离的最小值,dis[pos][2]为到达点$pos$的父亲的父亲的最小值,以此类推。

但这段代码有致命的缺陷——不能够求解先往下再往上的情况(如:$2 \rightarrow 5 \rightarrow 1$​)

image-20211028113403257

HACK数据①

1
2
3
4
5
6
7
8
9
7 6
3 6 2
1 5 1
1 7 5
2 5 3
1 3 1
1 4 1
1
2 3

因此,更换思路。

考虑每个点跑一次最短路?直接对每个点跑迪杰斯特拉最短路的话,使用堆优化,得到每个点到其他点的最小距离的复杂度在$O(n^2logn)$左右,如果跑$Floyd$连数组都开不下,考虑缩小点集的范围。

我们前文说到,两个点互达,必需要经过它们的其中一个公共祖先,由此我们考虑,能不能跑每个点到达它们子树中每一个点的最短路?

分析复杂度,设极限数据为最大深度$maxdep=20$​​​​​(此处 定义根节点$dep=1$​​)的完全满二叉树。

  1. 最后一层有$2^{maxdep - 1}$​​个点

  2. 每个点的子树大小为$1$​​(包括本身),则执行次数约为$2 ^ {maxdep-1} \times (1 * log (1) )$​​​

  3. 同理可推,倒数第二层有$2^{maxdep-2}$​​个点,子树大小为$3$​​(包括本身),则执行次数约为为$2^{maxdep-2} \times (3 * log(3))$​​​

我们整合一下,得到总的操作次数为:

$\sum_{i=0}^{maxdep - 1} 2^i \times (2^{maxdep - i} - 1) \times log(2^{maxdep - i})$​​

$=\sum_{i=0}^{maxdep - 1} (2^{maxdep} - 2^i) \times (maxdep - i)$​

$\leq (maxdep - 1) \times ((maxdep - 1) \times 2 ^ {maxdep} - \sum_{i=0}^{maxdep - 1} 2^i))$​​

$=(maxdep - 1) \times ((maxdep - 1) \times 2^{maxdep} - 2^{maxdep} + 1)$​

$\leq 2^{maxdep} \times (maxdep - 1) ^ 2$​

$\approx nlog^2n$

发现数量级在$10^7$,可以通过该题,也就是说我们只需要对每个点跑一次最短路,计算某个子树的根节点到子树中所有点的最短路径就可以AC该题。

HACK数据②

顺便提供两组HACK数据:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
7 11
2 4 3
1 5 3
2 4 3
2 5 3
2 4 4
3 7 3
3 7 1
1 6 4
1 3 2
3 6 1
1 4 3
1
6 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
15 18
6 12 1
4 9 4
2 8 3
4 8 3
3 14 3
3 6 5
6 12 2
7 14 1
1 3 3
7 14 1
6 12 5
2 8 2
4 8 2
4 9 3
1 10 3
1 4 5
4 8 5
1 9 1
1
2 10

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/* vegetable1024 | liushan.site | Maybe Lovely? */

#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
#pragma GCC target("avx", "sse2")
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)

#include <bits/stdc++.h>
#define maxn 100005
#define int long long
using namespace std;
int read(){
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}
int n, m, q, k, head[maxn * 4];
int dep[maxn], fa[maxn][20];
struct Edge{
int to;
int nxt;
int weight;
}E[maxn * 4];
void Build(int u, int v, int w){
E[k].to = v;
E[k].nxt = head[u];
E[k].weight = w;
head[u] = k++;
}
struct Node{
int now;
int dis;
};
bool operator < (const Node &A, const Node &B){
return A.dis > B.dis;
}
priority_queue<Node> q1;
bool check(int now, int nxt){
if(nxt >= now)
return (fa[nxt][dep[nxt] - dep[now]] == now);
return false;
}
int dis[maxn], INF = (1LL << 60);
map<int, int> finaldis[maxn];
void init(int pos){
if(pos > n) return;
dis[pos] = INF;
init((pos << 1));
init((pos << 1) + 1);
}
void record(int s, int pos){
if(pos > n) return;
finaldis[s][pos] = dis[pos];
record(s, (pos << 1));
record(s, (pos << 1) + 1);
}
void Dijstra(int rt){
init(rt); dis[rt] = 0;
q1.push((Node){rt, 0});
while(!q1.empty()){
Node tmp = q1.top(); q1.pop();
int now = tmp.now, dist = tmp.dis;
if(dist > dis[now]) continue;
for(int i = head[now]; ~i; i = E[i].nxt){
if(!check(rt, E[i].to)) continue;
if(dis[E[i].to] > dis[now] + E[i].weight){
dis[E[i].to] = dis[now] + E[i].weight;
q1.push((Node){E[i].to, dis[E[i].to]});
}
}
}
record(rt, rt);
}
int getlca(int r1, int r2){
vector<int> v1, v2, v3;
bool fir1 = false, fir2 = false;
for(int i = 18; i >= 0; i--){
if(r1 & (1 << i)) v1.push_back(1), fir1 = true;
else if(fir1) v1.push_back(0);
if(r2 & (1 << i)) v2.push_back(1), fir2 = true;
else if(fir2) v2.push_back(0);
}
int minn = min(v1.size(), v2.size());
for(int i = 0; i < minn; i++){
if(v1[i] != v2[i]) break;
v3.push_back(v1[i]);
}
int anslen = v3.size(), res = 0;
for(int i = anslen - 1, cnt = 0; i >= 0; i--, cnt++){
if(v3[i]) res += (1 << cnt);
}
return res;
}
signed main(void)
{
memset(head, -1, sizeof(head));
for(int i = 0; i <= 100000; i++) dis[i] = INF;
n = read(); m = read();
for(int i = 1; i <= n; i++){
int now = i, cnt = 0;
while(now){
fa[i][cnt++] = now; dep[i]++; now /= 2;
}
}
for(int i = 1; i <= m; i++){
int u = read(), v = read(), w = read();
Build(u, v, w);
Build(v, u, w);
}
for(int i = n; i >= 1; i--) Dijstra(i);
q = read();
while(q--){
int s = read(), t = read(), ans = (1LL << 60);
int lca = getlca(s, t);
while(lca){
int dis1 = finaldis[lca].count(s) ? finaldis[lca][s] : INF;
int dis2 = finaldis[lca].count(t) ? finaldis[lca][t] : INF;
ans = min(ans, dis1 + dis2);
lca /= 2;
}
printf("%lld\n", ans >= INF ? -1LL : ans);
}
return 0;
}

对拍器

中途因为各种BUG没调出来,上网找了个$std$​用来对拍,顺便把对拍的代码都放在这里,希望对读者有用…

fcc.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//fcc.cpp
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
int cnt = 0;
do{
printf("Case #%d:\n", ++cnt);
system("maker.exe");
system("my.exe < data.in > my.out");
system("std.exe < data.in > std.out");
//system("type data.in");
//system("type my.out");
} while (!system("fc my.out std.out"));
return 0;
}

maker.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//maker.cpp
#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;
int _r(int a, int b){
return (rand() % (b - a + 1)) + a;
}
int n, m;
vector<int> s;
void getson(int ss, int now){
if(now > n) return;
if(now != ss) s.push_back(now);
getson(ss, now * 2);
getson(ss, now * 2 + 1);
}
int son(int now){
s.clear();
getson(now, now);
int siz = s.size();
//cout << siz << endl;
return s[_r(1, siz) - 1];
}
signed main(void)
{
//time_t now = time(NULL);
//cout << now << endl;
srand(time(NULL));
freopen("data.in", "w", stdout);
n = (int)pow(2, _r(2, 3)) - 1;
m = _r(n - 1, n + 5);
printf("%lld %lld\n", n, m);
int maxsize = (int)pow(2, floor(log2(1.0 * n) + 1.0));
for(int i = 1; i <= m; i++){
int u = _r(1, maxsize / 2 - 1);
int v = son(u);
//printf("GG");
int w = _r(1, 5);
printf("%lld %lld %lld\n", u, v, w);
}
int q = _r(1, 10);
printf("%lld\n", q);
for(int i = 1; i <= q; i++){
int _u = _r(1, n), _v = _r(1, n);
while(_u == _v) _u = _r(1, n), _v = _r(1, n);
printf("%lld %lld\n", _u, _v);
}
return 0;
}

另外两个程序是$std.cpp$(上网自寻)和$my.cpp$(自己的代码),然后编译后放到同一目录就可以了。

如果你觉得还不错,就请咕咕的作者喝杯咖啡吧QAQ