#include <iostream>
#include <cassert>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")
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]); }
inline 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];
}
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 |
5168 KB |
Output is correct |
3 |
Correct |
2 ms |
4956 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
2 ms |
4956 KB |
Output is correct |
6 |
Correct |
1 ms |
5212 KB |
Output is correct |
7 |
Correct |
1 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
4956 KB |
Output is correct |
10 |
Correct |
2 ms |
4956 KB |
Output is correct |
11 |
Correct |
2 ms |
4956 KB |
Output is correct |
12 |
Correct |
1 ms |
4952 KB |
Output is correct |
13 |
Correct |
1 ms |
5208 KB |
Output is correct |
14 |
Correct |
1 ms |
4956 KB |
Output is correct |
15 |
Correct |
2 ms |
4956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4956 KB |
Output is correct |
2 |
Correct |
2 ms |
5168 KB |
Output is correct |
3 |
Correct |
2 ms |
4956 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
2 ms |
4956 KB |
Output is correct |
6 |
Correct |
1 ms |
5212 KB |
Output is correct |
7 |
Correct |
1 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
4956 KB |
Output is correct |
10 |
Correct |
2 ms |
4956 KB |
Output is correct |
11 |
Correct |
2 ms |
4956 KB |
Output is correct |
12 |
Correct |
1 ms |
4952 KB |
Output is correct |
13 |
Correct |
1 ms |
5208 KB |
Output is correct |
14 |
Correct |
1 ms |
4956 KB |
Output is correct |
15 |
Correct |
2 ms |
4956 KB |
Output is correct |
16 |
Correct |
81 ms |
10924 KB |
Output is correct |
17 |
Correct |
317 ms |
26976 KB |
Output is correct |
18 |
Correct |
21 ms |
7004 KB |
Output is correct |
19 |
Correct |
66 ms |
11852 KB |
Output is correct |
20 |
Correct |
355 ms |
26908 KB |
Output is correct |
21 |
Correct |
137 ms |
15056 KB |
Output is correct |
22 |
Correct |
65 ms |
18260 KB |
Output is correct |
23 |
Correct |
288 ms |
26828 KB |
Output is correct |
24 |
Correct |
310 ms |
26828 KB |
Output is correct |
25 |
Correct |
295 ms |
26812 KB |
Output is correct |
26 |
Correct |
67 ms |
11624 KB |
Output is correct |
27 |
Correct |
67 ms |
11736 KB |
Output is correct |
28 |
Correct |
67 ms |
11980 KB |
Output is correct |
29 |
Correct |
70 ms |
11848 KB |
Output is correct |
30 |
Correct |
65 ms |
11848 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4956 KB |
Output is correct |
2 |
Correct |
2 ms |
4956 KB |
Output is correct |
3 |
Correct |
1 ms |
4956 KB |
Output is correct |
4 |
Correct |
1 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 |
2 ms |
4956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
129 ms |
14800 KB |
Output is correct |
2 |
Correct |
290 ms |
26312 KB |
Output is correct |
3 |
Correct |
262 ms |
26400 KB |
Output is correct |
4 |
Correct |
45 ms |
14672 KB |
Output is correct |
5 |
Correct |
280 ms |
26388 KB |
Output is correct |
6 |
Correct |
289 ms |
26568 KB |
Output is correct |
7 |
Correct |
254 ms |
26340 KB |
Output is correct |
8 |
Correct |
282 ms |
26552 KB |
Output is correct |
9 |
Correct |
296 ms |
26656 KB |
Output is correct |
10 |
Correct |
276 ms |
26464 KB |
Output is correct |
11 |
Correct |
338 ms |
26484 KB |
Output is correct |
12 |
Correct |
258 ms |
26320 KB |
Output is correct |
13 |
Correct |
283 ms |
26316 KB |
Output is correct |
14 |
Correct |
310 ms |
26368 KB |
Output is correct |
15 |
Correct |
308 ms |
26988 KB |
Output is correct |
16 |
Correct |
272 ms |
26384 KB |
Output is correct |
17 |
Correct |
257 ms |
26316 KB |
Output is correct |
18 |
Correct |
251 ms |
26316 KB |
Output is correct |
19 |
Correct |
44 ms |
17232 KB |
Output is correct |
20 |
Correct |
262 ms |
26316 KB |
Output is correct |
21 |
Correct |
234 ms |
26084 KB |
Output is correct |
22 |
Correct |
62 ms |
11720 KB |
Output is correct |
23 |
Correct |
44 ms |
11088 KB |
Output is correct |
24 |
Correct |
46 ms |
11728 KB |
Output is correct |
25 |
Correct |
47 ms |
11716 KB |
Output is correct |
26 |
Correct |
63 ms |
11600 KB |
Output is correct |
27 |
Correct |
47 ms |
16744 KB |
Output is correct |
28 |
Correct |
47 ms |
11684 KB |
Output is correct |
29 |
Correct |
43 ms |
15736 KB |
Output is correct |
30 |
Correct |
49 ms |
11724 KB |
Output is correct |
31 |
Correct |
41 ms |
15580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4956 KB |
Output is correct |
2 |
Correct |
2 ms |
5168 KB |
Output is correct |
3 |
Correct |
2 ms |
4956 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
2 ms |
4956 KB |
Output is correct |
6 |
Correct |
1 ms |
5212 KB |
Output is correct |
7 |
Correct |
1 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
4956 KB |
Output is correct |
10 |
Correct |
2 ms |
4956 KB |
Output is correct |
11 |
Correct |
2 ms |
4956 KB |
Output is correct |
12 |
Correct |
1 ms |
4952 KB |
Output is correct |
13 |
Correct |
1 ms |
5208 KB |
Output is correct |
14 |
Correct |
1 ms |
4956 KB |
Output is correct |
15 |
Correct |
2 ms |
4956 KB |
Output is correct |
16 |
Correct |
81 ms |
10924 KB |
Output is correct |
17 |
Correct |
317 ms |
26976 KB |
Output is correct |
18 |
Correct |
21 ms |
7004 KB |
Output is correct |
19 |
Correct |
66 ms |
11852 KB |
Output is correct |
20 |
Correct |
355 ms |
26908 KB |
Output is correct |
21 |
Correct |
137 ms |
15056 KB |
Output is correct |
22 |
Correct |
65 ms |
18260 KB |
Output is correct |
23 |
Correct |
288 ms |
26828 KB |
Output is correct |
24 |
Correct |
310 ms |
26828 KB |
Output is correct |
25 |
Correct |
295 ms |
26812 KB |
Output is correct |
26 |
Correct |
67 ms |
11624 KB |
Output is correct |
27 |
Correct |
67 ms |
11736 KB |
Output is correct |
28 |
Correct |
67 ms |
11980 KB |
Output is correct |
29 |
Correct |
70 ms |
11848 KB |
Output is correct |
30 |
Correct |
65 ms |
11848 KB |
Output is correct |
31 |
Correct |
1 ms |
4956 KB |
Output is correct |
32 |
Correct |
2 ms |
4956 KB |
Output is correct |
33 |
Correct |
1 ms |
4956 KB |
Output is correct |
34 |
Correct |
1 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 |
2 ms |
4956 KB |
Output is correct |
41 |
Correct |
129 ms |
14800 KB |
Output is correct |
42 |
Correct |
290 ms |
26312 KB |
Output is correct |
43 |
Correct |
262 ms |
26400 KB |
Output is correct |
44 |
Correct |
45 ms |
14672 KB |
Output is correct |
45 |
Correct |
280 ms |
26388 KB |
Output is correct |
46 |
Correct |
289 ms |
26568 KB |
Output is correct |
47 |
Correct |
254 ms |
26340 KB |
Output is correct |
48 |
Correct |
282 ms |
26552 KB |
Output is correct |
49 |
Correct |
296 ms |
26656 KB |
Output is correct |
50 |
Correct |
276 ms |
26464 KB |
Output is correct |
51 |
Correct |
338 ms |
26484 KB |
Output is correct |
52 |
Correct |
258 ms |
26320 KB |
Output is correct |
53 |
Correct |
283 ms |
26316 KB |
Output is correct |
54 |
Correct |
310 ms |
26368 KB |
Output is correct |
55 |
Correct |
308 ms |
26988 KB |
Output is correct |
56 |
Correct |
272 ms |
26384 KB |
Output is correct |
57 |
Correct |
257 ms |
26316 KB |
Output is correct |
58 |
Correct |
251 ms |
26316 KB |
Output is correct |
59 |
Correct |
44 ms |
17232 KB |
Output is correct |
60 |
Correct |
262 ms |
26316 KB |
Output is correct |
61 |
Correct |
234 ms |
26084 KB |
Output is correct |
62 |
Correct |
62 ms |
11720 KB |
Output is correct |
63 |
Correct |
44 ms |
11088 KB |
Output is correct |
64 |
Correct |
46 ms |
11728 KB |
Output is correct |
65 |
Correct |
47 ms |
11716 KB |
Output is correct |
66 |
Correct |
63 ms |
11600 KB |
Output is correct |
67 |
Correct |
47 ms |
16744 KB |
Output is correct |
68 |
Correct |
47 ms |
11684 KB |
Output is correct |
69 |
Correct |
43 ms |
15736 KB |
Output is correct |
70 |
Correct |
49 ms |
11724 KB |
Output is correct |
71 |
Correct |
41 ms |
15580 KB |
Output is correct |
72 |
Correct |
164 ms |
15212 KB |
Output is correct |
73 |
Correct |
317 ms |
26828 KB |
Output is correct |
74 |
Correct |
298 ms |
26920 KB |
Output is correct |
75 |
Correct |
274 ms |
26920 KB |
Output is correct |
76 |
Correct |
281 ms |
26828 KB |
Output is correct |
77 |
Correct |
317 ms |
26820 KB |
Output is correct |
78 |
Correct |
330 ms |
26872 KB |
Output is correct |
79 |
Correct |
301 ms |
26876 KB |
Output is correct |
80 |
Correct |
331 ms |
26952 KB |
Output is correct |
81 |
Correct |
291 ms |
27084 KB |
Output is correct |
82 |
Correct |
309 ms |
26900 KB |
Output is correct |
83 |
Correct |
340 ms |
27104 KB |
Output is correct |
84 |
Correct |
309 ms |
27088 KB |
Output is correct |
85 |
Correct |
343 ms |
26928 KB |
Output is correct |
86 |
Correct |
284 ms |
26924 KB |
Output is correct |
87 |
Correct |
344 ms |
26892 KB |
Output is correct |
88 |
Correct |
287 ms |
26832 KB |
Output is correct |
89 |
Correct |
99 ms |
16724 KB |
Output is correct |
90 |
Correct |
301 ms |
26828 KB |
Output is correct |
91 |
Correct |
302 ms |
26236 KB |
Output is correct |
92 |
Correct |
65 ms |
11724 KB |
Output is correct |
93 |
Correct |
93 ms |
12116 KB |
Output is correct |
94 |
Correct |
66 ms |
11728 KB |
Output is correct |
95 |
Correct |
87 ms |
11664 KB |
Output is correct |
96 |
Correct |
95 ms |
12176 KB |
Output is correct |
97 |
Correct |
104 ms |
15344 KB |
Output is correct |
98 |
Correct |
69 ms |
11720 KB |
Output is correct |
99 |
Correct |
119 ms |
17296 KB |
Output is correct |
100 |
Correct |
69 ms |
11788 KB |
Output is correct |