#include <iostream>
#include <cassert>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 100005
int c, n, m, k, Q, d[N], P[N], J[N], L[N], p[N], M[N], Y[N];
vector<tuple<int, int, int>> el;
vector<pair<int, int>> g[N];
priority_queue<pair<int, int>> q;
int fnd(int u) { return p[u] < 0 ? u : fnd(p[u]); }
int unn(int x, int y) { x=fnd(x),y=fnd(y); if(x==y)return 0;if(-p[x]>-p[y]) swap(x,y); p[y]+=p[x];p[x]=y;return 1;}
void dfs(int u)
{
for (auto [w, v] : g[u])
{
if (v == P[u]) continue;
P[v] = u, L[v] = L[u] + 1, Y[v] = w;
if (L[u] - L[J[u]] == L[J[u]] - L[J[J[u]]]) J[v] = J[J[u]], M[v] = min({w, M[u], M[J[u]]});
else J[v] = u, M[v] = w;
dfs(v);
}
}
int evacuate(int u, int v)
{
if (L[u] < L[v]) return evacuate(v, u);
int z = 2e9;
for (; L[u] > L[v]; )
{
if (L[J[u]] >= L[v]) z = min(z, M[u]), u = J[u];
else z = min(z, Y[u]), u = P[u];
}
assert(L[u] == L[v]);
for (; u != v; )
{
if (J[u] != J[v]) z = min(z, min(M[u], M[v])), u = J[u], v = J[v];
else z = min(z, min(Y[u], Y[v])), u = P[u], v = P[v];
}
return z;
}
int main()
{
memset(d, 63, sizeof d); memset(p, -1, sizeof p);
ShinLena;
cin >> n >> m;
el.resize(m);
for (auto &[w, u, v]: el) cin >> u >> v >> w, g[v].emplace_back(w, u), g[u].emplace_back(w, v);
for (int x = (cin >> k, 0); k--;) cin >> x, q.emplace(d[x] = 0, x);
for (; q.size(); )
{
auto [c, u] = q.top(); q.pop();
for (auto [w, v] : g[u]) if (w - c < d[v]) q.emplace(-(d[v] = w-c), v);
}
for (auto &[w, u, v] : el) w = -min(d[u], d[v]);
for (int i = 1; i <= n; ++i) g[i].clear();
sort(ALL(el));
for (auto &[w, u, v] : el)
{
if (unn(u, v))
{
g[u].emplace_back(-w, v), g[v].emplace_back(-w, u);
if (++c == n - 1) break;
}
}
J[1] = P[1] = 1; M[1] = 1e9; dfs(1);
cin >> Q;
for (int u, v; Q--;) cin >> u >> v, cout << evacuate(u, v) << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4956 KB |
Output is correct |
2 |
Correct |
2 ms |
5208 KB |
Output is correct |
3 |
Correct |
2 ms |
5212 KB |
Output is correct |
4 |
Correct |
1 ms |
4952 KB |
Output is correct |
5 |
Correct |
2 ms |
5212 KB |
Output is correct |
6 |
Correct |
2 ms |
5212 KB |
Output is correct |
7 |
Correct |
1 ms |
4952 KB |
Output is correct |
8 |
Correct |
1 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
5212 KB |
Output is correct |
10 |
Correct |
2 ms |
5220 KB |
Output is correct |
11 |
Correct |
2 ms |
5208 KB |
Output is correct |
12 |
Correct |
2 ms |
5212 KB |
Output is correct |
13 |
Correct |
2 ms |
5212 KB |
Output is correct |
14 |
Correct |
2 ms |
5208 KB |
Output is correct |
15 |
Correct |
2 ms |
5220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4956 KB |
Output is correct |
2 |
Correct |
2 ms |
5208 KB |
Output is correct |
3 |
Correct |
2 ms |
5212 KB |
Output is correct |
4 |
Correct |
1 ms |
4952 KB |
Output is correct |
5 |
Correct |
2 ms |
5212 KB |
Output is correct |
6 |
Correct |
2 ms |
5212 KB |
Output is correct |
7 |
Correct |
1 ms |
4952 KB |
Output is correct |
8 |
Correct |
1 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
5212 KB |
Output is correct |
10 |
Correct |
2 ms |
5220 KB |
Output is correct |
11 |
Correct |
2 ms |
5208 KB |
Output is correct |
12 |
Correct |
2 ms |
5212 KB |
Output is correct |
13 |
Correct |
2 ms |
5212 KB |
Output is correct |
14 |
Correct |
2 ms |
5208 KB |
Output is correct |
15 |
Correct |
2 ms |
5220 KB |
Output is correct |
16 |
Correct |
80 ms |
13776 KB |
Output is correct |
17 |
Correct |
287 ms |
36304 KB |
Output is correct |
18 |
Correct |
21 ms |
7772 KB |
Output is correct |
19 |
Correct |
77 ms |
14904 KB |
Output is correct |
20 |
Correct |
288 ms |
36300 KB |
Output is correct |
21 |
Correct |
145 ms |
19852 KB |
Output is correct |
22 |
Correct |
71 ms |
21164 KB |
Output is correct |
23 |
Correct |
293 ms |
36572 KB |
Output is correct |
24 |
Correct |
284 ms |
36296 KB |
Output is correct |
25 |
Correct |
292 ms |
36300 KB |
Output is correct |
26 |
Correct |
97 ms |
14436 KB |
Output is correct |
27 |
Correct |
67 ms |
14668 KB |
Output is correct |
28 |
Correct |
76 ms |
14456 KB |
Output is correct |
29 |
Correct |
78 ms |
14704 KB |
Output is correct |
30 |
Correct |
95 ms |
14664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4956 KB |
Output is correct |
2 |
Correct |
1 ms |
4956 KB |
Output is correct |
3 |
Correct |
1 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4956 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
1 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
4956 KB |
Output is correct |
9 |
Correct |
1 ms |
4956 KB |
Output is correct |
10 |
Correct |
1 ms |
4956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
132 ms |
17940 KB |
Output is correct |
2 |
Correct |
313 ms |
34504 KB |
Output is correct |
3 |
Correct |
245 ms |
34700 KB |
Output is correct |
4 |
Correct |
41 ms |
16212 KB |
Output is correct |
5 |
Correct |
278 ms |
34644 KB |
Output is correct |
6 |
Correct |
320 ms |
34600 KB |
Output is correct |
7 |
Correct |
261 ms |
34684 KB |
Output is correct |
8 |
Correct |
338 ms |
34544 KB |
Output is correct |
9 |
Correct |
257 ms |
34612 KB |
Output is correct |
10 |
Correct |
308 ms |
34512 KB |
Output is correct |
11 |
Correct |
246 ms |
34508 KB |
Output is correct |
12 |
Correct |
267 ms |
34536 KB |
Output is correct |
13 |
Correct |
253 ms |
34576 KB |
Output is correct |
14 |
Correct |
275 ms |
34568 KB |
Output is correct |
15 |
Correct |
275 ms |
35444 KB |
Output is correct |
16 |
Correct |
276 ms |
34504 KB |
Output is correct |
17 |
Correct |
248 ms |
34508 KB |
Output is correct |
18 |
Correct |
265 ms |
34536 KB |
Output is correct |
19 |
Correct |
36 ms |
18796 KB |
Output is correct |
20 |
Correct |
258 ms |
34524 KB |
Output is correct |
21 |
Correct |
262 ms |
34764 KB |
Output is correct |
22 |
Correct |
47 ms |
13232 KB |
Output is correct |
23 |
Correct |
53 ms |
12592 KB |
Output is correct |
24 |
Correct |
47 ms |
13264 KB |
Output is correct |
25 |
Correct |
46 ms |
13292 KB |
Output is correct |
26 |
Correct |
49 ms |
13244 KB |
Output is correct |
27 |
Correct |
43 ms |
18364 KB |
Output is correct |
28 |
Correct |
51 ms |
13252 KB |
Output is correct |
29 |
Correct |
51 ms |
17232 KB |
Output is correct |
30 |
Correct |
67 ms |
13260 KB |
Output is correct |
31 |
Correct |
42 ms |
17240 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4956 KB |
Output is correct |
2 |
Correct |
2 ms |
5208 KB |
Output is correct |
3 |
Correct |
2 ms |
5212 KB |
Output is correct |
4 |
Correct |
1 ms |
4952 KB |
Output is correct |
5 |
Correct |
2 ms |
5212 KB |
Output is correct |
6 |
Correct |
2 ms |
5212 KB |
Output is correct |
7 |
Correct |
1 ms |
4952 KB |
Output is correct |
8 |
Correct |
1 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
5212 KB |
Output is correct |
10 |
Correct |
2 ms |
5220 KB |
Output is correct |
11 |
Correct |
2 ms |
5208 KB |
Output is correct |
12 |
Correct |
2 ms |
5212 KB |
Output is correct |
13 |
Correct |
2 ms |
5212 KB |
Output is correct |
14 |
Correct |
2 ms |
5208 KB |
Output is correct |
15 |
Correct |
2 ms |
5220 KB |
Output is correct |
16 |
Correct |
80 ms |
13776 KB |
Output is correct |
17 |
Correct |
287 ms |
36304 KB |
Output is correct |
18 |
Correct |
21 ms |
7772 KB |
Output is correct |
19 |
Correct |
77 ms |
14904 KB |
Output is correct |
20 |
Correct |
288 ms |
36300 KB |
Output is correct |
21 |
Correct |
145 ms |
19852 KB |
Output is correct |
22 |
Correct |
71 ms |
21164 KB |
Output is correct |
23 |
Correct |
293 ms |
36572 KB |
Output is correct |
24 |
Correct |
284 ms |
36296 KB |
Output is correct |
25 |
Correct |
292 ms |
36300 KB |
Output is correct |
26 |
Correct |
97 ms |
14436 KB |
Output is correct |
27 |
Correct |
67 ms |
14668 KB |
Output is correct |
28 |
Correct |
76 ms |
14456 KB |
Output is correct |
29 |
Correct |
78 ms |
14704 KB |
Output is correct |
30 |
Correct |
95 ms |
14664 KB |
Output is correct |
31 |
Correct |
1 ms |
4956 KB |
Output is correct |
32 |
Correct |
1 ms |
4956 KB |
Output is correct |
33 |
Correct |
1 ms |
4956 KB |
Output is correct |
34 |
Correct |
2 ms |
4956 KB |
Output is correct |
35 |
Correct |
1 ms |
4956 KB |
Output is correct |
36 |
Correct |
1 ms |
4956 KB |
Output is correct |
37 |
Correct |
1 ms |
4956 KB |
Output is correct |
38 |
Correct |
1 ms |
4956 KB |
Output is correct |
39 |
Correct |
1 ms |
4956 KB |
Output is correct |
40 |
Correct |
1 ms |
4956 KB |
Output is correct |
41 |
Correct |
132 ms |
17940 KB |
Output is correct |
42 |
Correct |
313 ms |
34504 KB |
Output is correct |
43 |
Correct |
245 ms |
34700 KB |
Output is correct |
44 |
Correct |
41 ms |
16212 KB |
Output is correct |
45 |
Correct |
278 ms |
34644 KB |
Output is correct |
46 |
Correct |
320 ms |
34600 KB |
Output is correct |
47 |
Correct |
261 ms |
34684 KB |
Output is correct |
48 |
Correct |
338 ms |
34544 KB |
Output is correct |
49 |
Correct |
257 ms |
34612 KB |
Output is correct |
50 |
Correct |
308 ms |
34512 KB |
Output is correct |
51 |
Correct |
246 ms |
34508 KB |
Output is correct |
52 |
Correct |
267 ms |
34536 KB |
Output is correct |
53 |
Correct |
253 ms |
34576 KB |
Output is correct |
54 |
Correct |
275 ms |
34568 KB |
Output is correct |
55 |
Correct |
275 ms |
35444 KB |
Output is correct |
56 |
Correct |
276 ms |
34504 KB |
Output is correct |
57 |
Correct |
248 ms |
34508 KB |
Output is correct |
58 |
Correct |
265 ms |
34536 KB |
Output is correct |
59 |
Correct |
36 ms |
18796 KB |
Output is correct |
60 |
Correct |
258 ms |
34524 KB |
Output is correct |
61 |
Correct |
262 ms |
34764 KB |
Output is correct |
62 |
Correct |
47 ms |
13232 KB |
Output is correct |
63 |
Correct |
53 ms |
12592 KB |
Output is correct |
64 |
Correct |
47 ms |
13264 KB |
Output is correct |
65 |
Correct |
46 ms |
13292 KB |
Output is correct |
66 |
Correct |
49 ms |
13244 KB |
Output is correct |
67 |
Correct |
43 ms |
18364 KB |
Output is correct |
68 |
Correct |
51 ms |
13252 KB |
Output is correct |
69 |
Correct |
51 ms |
17232 KB |
Output is correct |
70 |
Correct |
67 ms |
13260 KB |
Output is correct |
71 |
Correct |
42 ms |
17240 KB |
Output is correct |
72 |
Correct |
141 ms |
19924 KB |
Output is correct |
73 |
Correct |
329 ms |
36300 KB |
Output is correct |
74 |
Correct |
314 ms |
36344 KB |
Output is correct |
75 |
Correct |
334 ms |
36264 KB |
Output is correct |
76 |
Correct |
304 ms |
36144 KB |
Output is correct |
77 |
Correct |
363 ms |
36224 KB |
Output is correct |
78 |
Correct |
322 ms |
36228 KB |
Output is correct |
79 |
Correct |
283 ms |
36300 KB |
Output is correct |
80 |
Correct |
329 ms |
36296 KB |
Output is correct |
81 |
Correct |
320 ms |
36244 KB |
Output is correct |
82 |
Correct |
347 ms |
36516 KB |
Output is correct |
83 |
Correct |
294 ms |
36296 KB |
Output is correct |
84 |
Correct |
336 ms |
36320 KB |
Output is correct |
85 |
Correct |
317 ms |
36272 KB |
Output is correct |
86 |
Correct |
295 ms |
36252 KB |
Output is correct |
87 |
Correct |
358 ms |
36396 KB |
Output is correct |
88 |
Correct |
317 ms |
36188 KB |
Output is correct |
89 |
Correct |
100 ms |
19640 KB |
Output is correct |
90 |
Correct |
314 ms |
36332 KB |
Output is correct |
91 |
Correct |
282 ms |
36296 KB |
Output is correct |
92 |
Correct |
70 ms |
14660 KB |
Output is correct |
93 |
Correct |
94 ms |
14944 KB |
Output is correct |
94 |
Correct |
75 ms |
14408 KB |
Output is correct |
95 |
Correct |
89 ms |
14660 KB |
Output is correct |
96 |
Correct |
105 ms |
14928 KB |
Output is correct |
97 |
Correct |
105 ms |
18260 KB |
Output is correct |
98 |
Correct |
70 ms |
14408 KB |
Output is correct |
99 |
Correct |
104 ms |
20180 KB |
Output is correct |
100 |
Correct |
67 ms |
14700 KB |
Output is correct |