[NOI2018]归程

题解部分

这里是原题QwQ
一看到这道题 。。我。。我就不会做了 显然我们要先跑一遍最短路,得到每一个点到1的最短距离
然后呢?
我们要在这道题中用到一个叫做 Kruskal重构树 的黑科技,具体内容可以参照%%%

在学习了这个黑科技之后,我们来考虑一下它所要用在本题中的优秀性质。

  • 对于任意一个非叶子结点,它的优先级小于等于它的子树中任意一个结点

  • 换一种说法,我们在树上任选一条链,其上结点优先级具有单调性

简单的说,如果我们以海拔为关键字对边从大到小排序,然后构建出一颗Kruskal重构树,那么对于这颗树上的任意一个结点,如果它是合法的,那么它的子树中任意一个结点都是合法的
也就是说,对于我们所查询的结点,我们找到它的深度最浅的并且海拔大于p的祖先,那么在这个祖先的子树中的任意一个结点我们都可以不消耗任何代价到达
也就是也就是说,这颗子树中任意一个结点到1的最小代价就是这颗子树中到1最近的那个结点到1的代价

没有$\sum$的题解还能叫题解吗.jpg
对于如何找到它的满足条件的祖先,我们可以考虑使用我们可爱的倍增算法~~~

附上代码.png

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
#include <cstdio> 
#include <algorithm>
#include <cstring>

struct iostream {
static const int _SIZE = 1 << 26;
char *p1, *p2;
char ibuf[_SIZE], obuf[_SIZE];

iostream() : p1(ibuf), p2(obuf) {
#ifndef ONLINE_JUDGE
freopen("testdata.in", "r", stdin);
//freopen("testdata1.out", "w", stdout);
#endif
ibuf[fread(ibuf, 1, _SIZE, stdin)] = '\0';
}

~iostream() {
fwrite(obuf, 1, p2 - obuf, stdout);
}

inline char getchar() {
return *p1++;
}

template <typename _T>
iostream & operator >> (_T &x) {
static char c = getchar(); x = 0; bool flag = 0;
while (c < '0' || c > '9') (c == '-') && (flag = 1), c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
(flag) && (x = -x);
return *this;
}

inline void putchar(char x) {
*p2++ = x;
}

template <typename _T>
iostream & operator << (_T x) {
static char buf[19 ]; register char *p3 = buf;
if (x != 0) {
if (x < 0) putchar('-'), x = -x;
while (x) {
*p3++ = x % 10 + '0';
x /= 10;
}
while (p3 != buf) putchar(*--p3);
} else putchar('0');
putchar(' ');
return *this;
}
} IO;

static const int N = 200009, M = 400009 ;

struct Graph {
int cnt;
int head[N], nxt[M << 1], to[M << 1], val[M << 1];

void add(int a, int b, int c) {
int u = head[a], v = ++cnt;
nxt[v] = u, to[v] = b, val[v] = c;
head[a] = v;
}

void clear() {
cnt = 0;
memset(head, 0, sizeof(head));
memset(nxt, 0, sizeof(nxt));
memset(to, 0, sizeof(to));
memset(val, 0, sizeof(val));
}

void print(int lim) {
for (int i = 1; i <= lim; i++) {
for (int j = head[i]; j; j = nxt[j]) {
printf("%d -> %d : %d\n", i, to[j], val[j]);
}
}
}
};

struct Edge {
int u, v, val;

friend bool operator < (Edge a, Edge b) {
return a.val > b.val;
}
};

namespace UnionFind {
static int f[N << 1];

int find(int x) {
if (f[x]) return f[x] = find(f[x]);
return x;
}

void merge(int a, int b, int fa) {
f[a] = f[b] = fa;
}

void clear() {
memset(f, 0, sizeof(f));
}
}

namespace Dijkstra {
#define lson (u << 1)
#define rson (u << 1 | 1)
static int dis[N], min[N << 2];
inline void pushup(int u) {
if (min[lson] && min[rson]) min[u] = (dis[min[lson]] < dis[min[rson]]) ? min[lson] : min[rson];
else if (min[lson]) min[u] = min[lson];
else if (min[rson]) min[u] = min[rson];
else min[u] = 0;
}

void modify(int u, int L, int R, int pos, int x) {
if (L == R) {
min[u] = x;
return;
}
int mid = L + R >> 1;
if (pos <= mid) modify(lson, L, mid, pos, x);
else modify(rson, mid + 1, R, pos, x);
pushup(u);
}

void Dijkstra(int s, int lim, Graph &graph) {
for (int i = 1; i <= lim; i++) dis[i] = 0x7fffffff;
memset(min, 0, sizeof(min));
dis[s] = 0, modify(1, 1, lim, s, s);
for (int _i = 1; _i <= lim; _i++) {
int u = min[1];
modify(1, 1, lim, u, 0);
for (int i = graph.head[u]; i; i = graph.nxt[i]) {
int v = graph.to[i];
if (dis[v] > dis[u] + graph.val[i]) {
dis[v] = dis[u] + graph.val[i];
modify(1, 1, lim, v, v);
}
}
}
}
}

struct Kruskal {
static const int logs = 20;
int ch[N << 1][2], val[N << 1], min[N << 1];
int f[N << 1][logs + 9];

void dfs(int u) {
for (int i = 1; i <= logs; i++) f[u][i] = f[f[u][i - 1]][i - 1];
if (!ch[u][0]) min[u] = Dijkstra::dis[u];
else {
dfs(ch[u][0]), dfs(ch[u][1]);
min[u] = std::min(min[ch[u][0]], min[ch[u][1]]);
}
}

void build(Edge *E, int lim, int m) {
std::sort(E + 1, E + 1 + m);
for (int i = 1, j = 0; i <= m, j < lim - 1; i++) {
int fu = UnionFind::find(E[i].u), fv = UnionFind::find(E[i].v);
if (fu == fv) continue;
j++;
val[lim + j] = E[i].val, f[fu][0] = f[fv][0] = lim + j;
ch[lim + j][0] = fu, ch[lim + j][1] = fv;
UnionFind::merge(fu, fv, lim + j);
}
dfs(lim * 2 - 1);
}

int query(int u, int p) {
for (int i = logs; i >= 0; i--) {
if (!f[u][i] || val[f[u][i]] <= p) continue;
u = f[u][i];
}
return min[u];
}

void clear() {
memset(ch, 0, sizeof(ch));
memset(val, 0, sizeof(val));
memset(f, 0, sizeof(f));
memset(min, 0, sizeof(min));
}
};

int Test, n, m, q, K, S, lastans;
Edge E[M];
Graph G;
Kruskal T;

void init() {
lastans = 0;
G.clear();
T.clear();
UnionFind::clear();
}

int main() {
IO >> Test;
while (Test--) {
init();
IO >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, l, a;
IO >> u >> v >> l >> a;
E[i] = (Edge) {u, v, a};
G.add(u, v, l), G.add(v, u, l);
}
Dijkstra::Dijkstra(1, n, G);
T.build(E, n, m);
IO >> q >> K >> S;
while (q--) {
int v0, p0, v, p;
IO >> v0 >> p0;
v = (v0 + K * lastans - 1) % n + 1;
p = (p0 + K * lastans) % (S + 1);
lastans = T.query(v, p);
IO << lastans, IO.putchar('\n');
}
}
return 0;
}

吐槽部分

首先我想说,封装是个好东西

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
1   #include <cstdio>
2 #include <algorithm>
3 #include <cstring>
4
5 struct iostream {
53 } IO;
54
55 static const int N = 200009, M = 400009;
56
57 struct Graph {
82 };
83
84 struct Edge {
90 };
91
92 namespace UnionFind {
107 }
108
109 namespace Dijkstra {
147 }
148
149 struct Kruskal {
190 };
191
192 int Test, n, m, q, K, S, lastans;
193 Edge E[M];
194 Graph G;
195 Kruskal T;
196
197 void init() {
202 }
203
204 int main() {
228 }

这是我封装之后的代码,是不是炒鸡优美?
唯一想让人吐槽的是,仔细观察你会发现,IO部分写了48行,是这篇代码中最长的部分。。。。
这道题我在某谷上交了4次,第一次忘了init,第二次忘记清零cnt,第三次忘记清零lastans///
然后我发现自己在初赛倒计时两天的时候颓了一天的Kruskal重构树
mdzz
这道题用上了我两天的积蓄,昨天刚学的线段树优化Dijkstra今天就用上了