#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
const int N = 1e5 + 5;
const int INF = 1e9 + 5;
int n, m, k, q;
int g[N], d[N], a[N];
vector <pair <int, int>> adj[N];
// d(x) : shortest distance from x to a critical vertex
void dijkstra() {
for (int i = 1; i <= n; ++i) d[i] = INF;
using T = pair <int, int>;
priority_queue <T, vector <T>, greater <>> pq;
for (int i = 1; i <= k; ++i) {
d[g[i]] = 0;
pq.push({d[g[i]], g[i]});
}
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (du > d[u]) continue;
for (auto [w, v] : adj[u]) {
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
pq.push({d[v], v});
}
}
}
for (int i = 1; i <= n; ++i) a[i] = i;
sort(a + 1, a + 1 + n, [&] (int x, int y) {
return d[x] > d[y];
});
}
struct Query {
int s, t, l, r, mi, id;
} qs[N];
struct DisjointSet {
vector <int> pa, sz;
int n;
DisjointSet(int _n = 0) { init(_n); }
void init(int _n) {
n = _n;
sz.resize(n + 5, 1);
pa.resize(n + 5, 0);
iota(pa.begin(), pa.end(), 0);
}
int get(int u) { return (u == pa[u]? u : pa[u] = get(pa[u])); }
bool unite(int u, int v) {
u = get(u);
v = get(v);
if (u == v) return 0;
if (sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
pa[v] = u;
return 1;
}
};
int ans[N];
void solve() {
DisjointSet dsu(n);
// DSU storing all vertices having d[x] >= current best answer
for (int i = 1; i <= q; ++i) {
qs[i].mi = (qs[i].l + qs[i].r) / 2;
}
// sort queries according to mid
sort(qs + 1, qs + 1 + q, [&] (Query x, Query y){
return (x.mi > y.mi);
});
int j = 1;
vector <bool> vis(n + 5, 0);
for (int i = 1; i <= q; ++i) {
auto [s, t, l, r, mi, id] = qs[i];
if (l > r) continue;
while (j <= n && d[a[j]] >= mi) {
vis[a[j]] = 1;
for (auto [w, v] : adj[a[j]])
if (vis[v])
dsu.unite(v, a[j]);
++j;
}
if (vis[s] && vis[t] && dsu.get(s) == dsu.get(t)) {
ans[id] = mi;
qs[i].l = mi + 1;
}
else
qs[i].r = mi - 1;
}
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({w, v});
adj[v].push_back({w, u});
}
cin >> k;
for (int i = 1; i <= k; ++i) cin >> g[i];
dijkstra();
// for (int i = 1; i <= n; ++i) cout << d[i] << " \n"[i == n];
cin >> q;
for (int i = 1; i <= q; ++i) {
cin >> qs[i].s >> qs[i].t;
qs[i].l = 1; qs[i].r = INF;
qs[i].id = i;
}
for (int i = 1; i <= 30; ++i) {
solve();
}
for (int i = 1; i <= q; ++i)
cout << ans[i] << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5212 KB |
Output is correct |
2 |
Correct |
2 ms |
5388 KB |
Output is correct |
3 |
Correct |
3 ms |
5468 KB |
Output is correct |
4 |
Correct |
2 ms |
5380 KB |
Output is correct |
5 |
Correct |
3 ms |
5468 KB |
Output is correct |
6 |
Correct |
2 ms |
5396 KB |
Output is correct |
7 |
Correct |
2 ms |
5212 KB |
Output is correct |
8 |
Correct |
2 ms |
5212 KB |
Output is correct |
9 |
Correct |
3 ms |
5460 KB |
Output is correct |
10 |
Correct |
3 ms |
5468 KB |
Output is correct |
11 |
Correct |
3 ms |
5468 KB |
Output is correct |
12 |
Correct |
2 ms |
5468 KB |
Output is correct |
13 |
Correct |
3 ms |
5392 KB |
Output is correct |
14 |
Correct |
3 ms |
5392 KB |
Output is correct |
15 |
Correct |
3 ms |
5476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5212 KB |
Output is correct |
2 |
Correct |
2 ms |
5388 KB |
Output is correct |
3 |
Correct |
3 ms |
5468 KB |
Output is correct |
4 |
Correct |
2 ms |
5380 KB |
Output is correct |
5 |
Correct |
3 ms |
5468 KB |
Output is correct |
6 |
Correct |
2 ms |
5396 KB |
Output is correct |
7 |
Correct |
2 ms |
5212 KB |
Output is correct |
8 |
Correct |
2 ms |
5212 KB |
Output is correct |
9 |
Correct |
3 ms |
5460 KB |
Output is correct |
10 |
Correct |
3 ms |
5468 KB |
Output is correct |
11 |
Correct |
3 ms |
5468 KB |
Output is correct |
12 |
Correct |
2 ms |
5468 KB |
Output is correct |
13 |
Correct |
3 ms |
5392 KB |
Output is correct |
14 |
Correct |
3 ms |
5392 KB |
Output is correct |
15 |
Correct |
3 ms |
5476 KB |
Output is correct |
16 |
Correct |
261 ms |
13152 KB |
Output is correct |
17 |
Correct |
584 ms |
30932 KB |
Output is correct |
18 |
Correct |
35 ms |
7576 KB |
Output is correct |
19 |
Correct |
181 ms |
14148 KB |
Output is correct |
20 |
Correct |
560 ms |
30736 KB |
Output is correct |
21 |
Correct |
259 ms |
18536 KB |
Output is correct |
22 |
Correct |
216 ms |
13288 KB |
Output is correct |
23 |
Correct |
558 ms |
30888 KB |
Output is correct |
24 |
Correct |
521 ms |
30848 KB |
Output is correct |
25 |
Correct |
423 ms |
30852 KB |
Output is correct |
26 |
Correct |
151 ms |
14140 KB |
Output is correct |
27 |
Correct |
185 ms |
14268 KB |
Output is correct |
28 |
Correct |
156 ms |
14140 KB |
Output is correct |
29 |
Correct |
153 ms |
14124 KB |
Output is correct |
30 |
Correct |
189 ms |
14276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5208 KB |
Output is correct |
2 |
Correct |
1 ms |
5212 KB |
Output is correct |
3 |
Correct |
1 ms |
5212 KB |
Output is correct |
4 |
Correct |
2 ms |
5212 KB |
Output is correct |
5 |
Correct |
1 ms |
5212 KB |
Output is correct |
6 |
Correct |
2 ms |
5212 KB |
Output is correct |
7 |
Correct |
1 ms |
5212 KB |
Output is correct |
8 |
Correct |
1 ms |
5212 KB |
Output is correct |
9 |
Correct |
1 ms |
5212 KB |
Output is correct |
10 |
Correct |
1 ms |
5208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
167 ms |
16652 KB |
Output is correct |
2 |
Correct |
339 ms |
28912 KB |
Output is correct |
3 |
Correct |
303 ms |
29348 KB |
Output is correct |
4 |
Correct |
103 ms |
11728 KB |
Output is correct |
5 |
Correct |
338 ms |
29104 KB |
Output is correct |
6 |
Correct |
292 ms |
29216 KB |
Output is correct |
7 |
Correct |
254 ms |
29132 KB |
Output is correct |
8 |
Correct |
252 ms |
29100 KB |
Output is correct |
9 |
Correct |
302 ms |
28924 KB |
Output is correct |
10 |
Correct |
335 ms |
29096 KB |
Output is correct |
11 |
Correct |
395 ms |
29088 KB |
Output is correct |
12 |
Correct |
389 ms |
29152 KB |
Output is correct |
13 |
Correct |
342 ms |
28956 KB |
Output is correct |
14 |
Correct |
273 ms |
29120 KB |
Output is correct |
15 |
Correct |
352 ms |
29168 KB |
Output is correct |
16 |
Correct |
336 ms |
29104 KB |
Output is correct |
17 |
Correct |
312 ms |
29100 KB |
Output is correct |
18 |
Correct |
254 ms |
28916 KB |
Output is correct |
19 |
Correct |
63 ms |
11720 KB |
Output is correct |
20 |
Correct |
307 ms |
29160 KB |
Output is correct |
21 |
Correct |
225 ms |
29820 KB |
Output is correct |
22 |
Correct |
68 ms |
12380 KB |
Output is correct |
23 |
Correct |
128 ms |
12228 KB |
Output is correct |
24 |
Correct |
55 ms |
12352 KB |
Output is correct |
25 |
Correct |
60 ms |
12340 KB |
Output is correct |
26 |
Correct |
97 ms |
12296 KB |
Output is correct |
27 |
Correct |
92 ms |
11716 KB |
Output is correct |
28 |
Correct |
57 ms |
12520 KB |
Output is correct |
29 |
Correct |
81 ms |
11724 KB |
Output is correct |
30 |
Correct |
87 ms |
12424 KB |
Output is correct |
31 |
Correct |
84 ms |
11724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5212 KB |
Output is correct |
2 |
Correct |
2 ms |
5388 KB |
Output is correct |
3 |
Correct |
3 ms |
5468 KB |
Output is correct |
4 |
Correct |
2 ms |
5380 KB |
Output is correct |
5 |
Correct |
3 ms |
5468 KB |
Output is correct |
6 |
Correct |
2 ms |
5396 KB |
Output is correct |
7 |
Correct |
2 ms |
5212 KB |
Output is correct |
8 |
Correct |
2 ms |
5212 KB |
Output is correct |
9 |
Correct |
3 ms |
5460 KB |
Output is correct |
10 |
Correct |
3 ms |
5468 KB |
Output is correct |
11 |
Correct |
3 ms |
5468 KB |
Output is correct |
12 |
Correct |
2 ms |
5468 KB |
Output is correct |
13 |
Correct |
3 ms |
5392 KB |
Output is correct |
14 |
Correct |
3 ms |
5392 KB |
Output is correct |
15 |
Correct |
3 ms |
5476 KB |
Output is correct |
16 |
Correct |
261 ms |
13152 KB |
Output is correct |
17 |
Correct |
584 ms |
30932 KB |
Output is correct |
18 |
Correct |
35 ms |
7576 KB |
Output is correct |
19 |
Correct |
181 ms |
14148 KB |
Output is correct |
20 |
Correct |
560 ms |
30736 KB |
Output is correct |
21 |
Correct |
259 ms |
18536 KB |
Output is correct |
22 |
Correct |
216 ms |
13288 KB |
Output is correct |
23 |
Correct |
558 ms |
30888 KB |
Output is correct |
24 |
Correct |
521 ms |
30848 KB |
Output is correct |
25 |
Correct |
423 ms |
30852 KB |
Output is correct |
26 |
Correct |
151 ms |
14140 KB |
Output is correct |
27 |
Correct |
185 ms |
14268 KB |
Output is correct |
28 |
Correct |
156 ms |
14140 KB |
Output is correct |
29 |
Correct |
153 ms |
14124 KB |
Output is correct |
30 |
Correct |
189 ms |
14276 KB |
Output is correct |
31 |
Correct |
1 ms |
5208 KB |
Output is correct |
32 |
Correct |
1 ms |
5212 KB |
Output is correct |
33 |
Correct |
1 ms |
5212 KB |
Output is correct |
34 |
Correct |
2 ms |
5212 KB |
Output is correct |
35 |
Correct |
1 ms |
5212 KB |
Output is correct |
36 |
Correct |
2 ms |
5212 KB |
Output is correct |
37 |
Correct |
1 ms |
5212 KB |
Output is correct |
38 |
Correct |
1 ms |
5212 KB |
Output is correct |
39 |
Correct |
1 ms |
5212 KB |
Output is correct |
40 |
Correct |
1 ms |
5208 KB |
Output is correct |
41 |
Correct |
167 ms |
16652 KB |
Output is correct |
42 |
Correct |
339 ms |
28912 KB |
Output is correct |
43 |
Correct |
303 ms |
29348 KB |
Output is correct |
44 |
Correct |
103 ms |
11728 KB |
Output is correct |
45 |
Correct |
338 ms |
29104 KB |
Output is correct |
46 |
Correct |
292 ms |
29216 KB |
Output is correct |
47 |
Correct |
254 ms |
29132 KB |
Output is correct |
48 |
Correct |
252 ms |
29100 KB |
Output is correct |
49 |
Correct |
302 ms |
28924 KB |
Output is correct |
50 |
Correct |
335 ms |
29096 KB |
Output is correct |
51 |
Correct |
395 ms |
29088 KB |
Output is correct |
52 |
Correct |
389 ms |
29152 KB |
Output is correct |
53 |
Correct |
342 ms |
28956 KB |
Output is correct |
54 |
Correct |
273 ms |
29120 KB |
Output is correct |
55 |
Correct |
352 ms |
29168 KB |
Output is correct |
56 |
Correct |
336 ms |
29104 KB |
Output is correct |
57 |
Correct |
312 ms |
29100 KB |
Output is correct |
58 |
Correct |
254 ms |
28916 KB |
Output is correct |
59 |
Correct |
63 ms |
11720 KB |
Output is correct |
60 |
Correct |
307 ms |
29160 KB |
Output is correct |
61 |
Correct |
225 ms |
29820 KB |
Output is correct |
62 |
Correct |
68 ms |
12380 KB |
Output is correct |
63 |
Correct |
128 ms |
12228 KB |
Output is correct |
64 |
Correct |
55 ms |
12352 KB |
Output is correct |
65 |
Correct |
60 ms |
12340 KB |
Output is correct |
66 |
Correct |
97 ms |
12296 KB |
Output is correct |
67 |
Correct |
92 ms |
11716 KB |
Output is correct |
68 |
Correct |
57 ms |
12520 KB |
Output is correct |
69 |
Correct |
81 ms |
11724 KB |
Output is correct |
70 |
Correct |
87 ms |
12424 KB |
Output is correct |
71 |
Correct |
84 ms |
11724 KB |
Output is correct |
72 |
Correct |
314 ms |
18360 KB |
Output is correct |
73 |
Correct |
509 ms |
30756 KB |
Output is correct |
74 |
Correct |
507 ms |
30692 KB |
Output is correct |
75 |
Correct |
510 ms |
30912 KB |
Output is correct |
76 |
Correct |
466 ms |
30688 KB |
Output is correct |
77 |
Correct |
508 ms |
30840 KB |
Output is correct |
78 |
Correct |
486 ms |
30692 KB |
Output is correct |
79 |
Correct |
485 ms |
30724 KB |
Output is correct |
80 |
Correct |
535 ms |
30816 KB |
Output is correct |
81 |
Correct |
519 ms |
30960 KB |
Output is correct |
82 |
Correct |
493 ms |
30972 KB |
Output is correct |
83 |
Correct |
465 ms |
30776 KB |
Output is correct |
84 |
Correct |
492 ms |
30880 KB |
Output is correct |
85 |
Correct |
454 ms |
31000 KB |
Output is correct |
86 |
Correct |
547 ms |
30748 KB |
Output is correct |
87 |
Correct |
471 ms |
30748 KB |
Output is correct |
88 |
Correct |
625 ms |
30768 KB |
Output is correct |
89 |
Correct |
230 ms |
13176 KB |
Output is correct |
90 |
Correct |
594 ms |
30736 KB |
Output is correct |
91 |
Correct |
328 ms |
31256 KB |
Output is correct |
92 |
Correct |
180 ms |
14184 KB |
Output is correct |
93 |
Correct |
325 ms |
13668 KB |
Output is correct |
94 |
Correct |
160 ms |
13904 KB |
Output is correct |
95 |
Correct |
186 ms |
14184 KB |
Output is correct |
96 |
Correct |
247 ms |
13632 KB |
Output is correct |
97 |
Correct |
259 ms |
13116 KB |
Output is correct |
98 |
Correct |
174 ms |
14120 KB |
Output is correct |
99 |
Correct |
278 ms |
13224 KB |
Output is correct |
100 |
Correct |
166 ms |
14012 KB |
Output is correct |