#include <bits/stdc++.h>
using namespace std;
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
const int NM = 1e5, inf = 1e9+7, LIM = 1e8;
struct query{
int id, s, t, l, r, mid;
};
int n, m, k, g[NM+5], q;
vector <pii> adj[NM+5];
priority_queue <pii, vector <pii>, greater <pii> > Q;
int d[NM+5], a[NM+5];
bool fix[NM+5];
query b[NM+5];
int ans[NM+5];
int parent[NM+5], sz[NM+5];
bool on[NM+5];
void dijkstra(){
for (int i = 1; i <= n; i++) d[i] = +inf;
for (int i = 1; i <= k; i++){
d[g[i]] = 0;
Q.push(mp(0, g[i]));
}
while (true){
while (!Q.empty() && fix[Q.top().se]) Q.pop();
if (Q.empty()) break;
int u = Q.top().se; Q.pop();
fix[u] = 1;
for (pii _ : adj[u]){
int v = _.fi, w = _.se;
if (fix[v]) continue;
if (d[u]+w < d[v]){
d[v] = d[u]+w;
Q.push(mp(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];
});
}
bool cmp(query a, query b){
if (a.l > a.r) return 0;
if (b.l > b.r) return 1;
return a.mid > b.mid;
}
void make_set(int v){
parent[v] = v;
sz[v] = 1;
}
int find_set(int v){
return parent[v] == v ? v : parent[v] = find_set(parent[v]);
}
void union_sets(int u, int v){
u = find_set(u), v = find_set(v);
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
parent[v] = u;
sz[u] += sz[v];
}
void parallel_binary_search(){
for (int i = 1; i <= q; i++)
b[i].mid = (b[i].l+b[i].r)/2;
sort(b+1, b+1+q, cmp);
for (int i = 1; i <= n; i++){
make_set(i);
on[i] = 0;
}
int j = 1;
for (int i = 1; i <= q; i++){
if (b[i].l > b[i].r) break;
while (j <= n && d[a[j]] >= b[i].mid){
on[a[j]] = 1;
for (pii _ : adj[a[j]]){
int v = _.fi;
if (on[v]) union_sets(a[j], v);
}
j++;
}
if (on[b[i].s] && on[b[i].t] && find_set(b[i].s) == find_set(b[i].t)){
ans[b[i].id] = b[i].mid;
b[i].l = b[i].mid+1;
}
else b[i].r = b[i].mid-1;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
while (m--){
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back(mp(v, w));
adj[v].push_back(mp(u, w));
}
cin >> k;
for (int i = 1; i <= k; i++) cin >> g[i];
dijkstra();
cin >> q;
for (int i = 1; i <= q; i++){
cin >> b[i].s >> b[i].t;
b[i].id = i;
b[i].l = 1, b[i].r = LIM;
}
for (int i = 1; (1<<i) < 2*LIM; i++){
parallel_binary_search();
}
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7004 KB |
Output is correct |
2 |
Correct |
4 ms |
7004 KB |
Output is correct |
3 |
Correct |
3 ms |
7004 KB |
Output is correct |
4 |
Correct |
3 ms |
7128 KB |
Output is correct |
5 |
Correct |
3 ms |
7004 KB |
Output is correct |
6 |
Correct |
3 ms |
7000 KB |
Output is correct |
7 |
Correct |
2 ms |
7000 KB |
Output is correct |
8 |
Correct |
2 ms |
7004 KB |
Output is correct |
9 |
Correct |
4 ms |
7004 KB |
Output is correct |
10 |
Correct |
3 ms |
7004 KB |
Output is correct |
11 |
Correct |
4 ms |
7000 KB |
Output is correct |
12 |
Correct |
3 ms |
7004 KB |
Output is correct |
13 |
Correct |
3 ms |
7004 KB |
Output is correct |
14 |
Correct |
4 ms |
7004 KB |
Output is correct |
15 |
Correct |
4 ms |
7004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7004 KB |
Output is correct |
2 |
Correct |
4 ms |
7004 KB |
Output is correct |
3 |
Correct |
3 ms |
7004 KB |
Output is correct |
4 |
Correct |
3 ms |
7128 KB |
Output is correct |
5 |
Correct |
3 ms |
7004 KB |
Output is correct |
6 |
Correct |
3 ms |
7000 KB |
Output is correct |
7 |
Correct |
2 ms |
7000 KB |
Output is correct |
8 |
Correct |
2 ms |
7004 KB |
Output is correct |
9 |
Correct |
4 ms |
7004 KB |
Output is correct |
10 |
Correct |
3 ms |
7004 KB |
Output is correct |
11 |
Correct |
4 ms |
7000 KB |
Output is correct |
12 |
Correct |
3 ms |
7004 KB |
Output is correct |
13 |
Correct |
3 ms |
7004 KB |
Output is correct |
14 |
Correct |
4 ms |
7004 KB |
Output is correct |
15 |
Correct |
4 ms |
7004 KB |
Output is correct |
16 |
Correct |
284 ms |
14232 KB |
Output is correct |
17 |
Correct |
646 ms |
32204 KB |
Output is correct |
18 |
Correct |
40 ms |
9332 KB |
Output is correct |
19 |
Correct |
214 ms |
15428 KB |
Output is correct |
20 |
Correct |
670 ms |
32068 KB |
Output is correct |
21 |
Correct |
335 ms |
19660 KB |
Output is correct |
22 |
Correct |
282 ms |
14336 KB |
Output is correct |
23 |
Correct |
672 ms |
32052 KB |
Output is correct |
24 |
Correct |
680 ms |
32132 KB |
Output is correct |
25 |
Correct |
569 ms |
32196 KB |
Output is correct |
26 |
Correct |
229 ms |
15036 KB |
Output is correct |
27 |
Correct |
213 ms |
15296 KB |
Output is correct |
28 |
Correct |
282 ms |
15036 KB |
Output is correct |
29 |
Correct |
213 ms |
15168 KB |
Output is correct |
30 |
Correct |
220 ms |
15428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7000 KB |
Output is correct |
2 |
Correct |
2 ms |
7004 KB |
Output is correct |
3 |
Correct |
2 ms |
7140 KB |
Output is correct |
4 |
Correct |
2 ms |
7004 KB |
Output is correct |
5 |
Correct |
2 ms |
7000 KB |
Output is correct |
6 |
Correct |
2 ms |
7004 KB |
Output is correct |
7 |
Correct |
2 ms |
7004 KB |
Output is correct |
8 |
Correct |
2 ms |
7004 KB |
Output is correct |
9 |
Correct |
2 ms |
7004 KB |
Output is correct |
10 |
Correct |
2 ms |
7004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
149 ms |
17456 KB |
Output is correct |
2 |
Correct |
341 ms |
30408 KB |
Output is correct |
3 |
Correct |
339 ms |
30412 KB |
Output is correct |
4 |
Correct |
62 ms |
11860 KB |
Output is correct |
5 |
Correct |
414 ms |
30404 KB |
Output is correct |
6 |
Correct |
271 ms |
30392 KB |
Output is correct |
7 |
Correct |
286 ms |
30404 KB |
Output is correct |
8 |
Correct |
275 ms |
30464 KB |
Output is correct |
9 |
Correct |
280 ms |
30412 KB |
Output is correct |
10 |
Correct |
444 ms |
30572 KB |
Output is correct |
11 |
Correct |
421 ms |
30416 KB |
Output is correct |
12 |
Correct |
377 ms |
30512 KB |
Output is correct |
13 |
Correct |
341 ms |
30412 KB |
Output is correct |
14 |
Correct |
284 ms |
30452 KB |
Output is correct |
15 |
Correct |
379 ms |
30664 KB |
Output is correct |
16 |
Correct |
342 ms |
30412 KB |
Output is correct |
17 |
Correct |
289 ms |
30408 KB |
Output is correct |
18 |
Correct |
268 ms |
30412 KB |
Output is correct |
19 |
Correct |
41 ms |
11900 KB |
Output is correct |
20 |
Correct |
319 ms |
30432 KB |
Output is correct |
21 |
Correct |
273 ms |
31156 KB |
Output is correct |
22 |
Correct |
56 ms |
13640 KB |
Output is correct |
23 |
Correct |
95 ms |
12576 KB |
Output is correct |
24 |
Correct |
55 ms |
13636 KB |
Output is correct |
25 |
Correct |
56 ms |
13684 KB |
Output is correct |
26 |
Correct |
79 ms |
12624 KB |
Output is correct |
27 |
Correct |
67 ms |
11856 KB |
Output is correct |
28 |
Correct |
51 ms |
13636 KB |
Output is correct |
29 |
Correct |
64 ms |
11860 KB |
Output is correct |
30 |
Correct |
60 ms |
13616 KB |
Output is correct |
31 |
Correct |
65 ms |
11860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7004 KB |
Output is correct |
2 |
Correct |
4 ms |
7004 KB |
Output is correct |
3 |
Correct |
3 ms |
7004 KB |
Output is correct |
4 |
Correct |
3 ms |
7128 KB |
Output is correct |
5 |
Correct |
3 ms |
7004 KB |
Output is correct |
6 |
Correct |
3 ms |
7000 KB |
Output is correct |
7 |
Correct |
2 ms |
7000 KB |
Output is correct |
8 |
Correct |
2 ms |
7004 KB |
Output is correct |
9 |
Correct |
4 ms |
7004 KB |
Output is correct |
10 |
Correct |
3 ms |
7004 KB |
Output is correct |
11 |
Correct |
4 ms |
7000 KB |
Output is correct |
12 |
Correct |
3 ms |
7004 KB |
Output is correct |
13 |
Correct |
3 ms |
7004 KB |
Output is correct |
14 |
Correct |
4 ms |
7004 KB |
Output is correct |
15 |
Correct |
4 ms |
7004 KB |
Output is correct |
16 |
Correct |
284 ms |
14232 KB |
Output is correct |
17 |
Correct |
646 ms |
32204 KB |
Output is correct |
18 |
Correct |
40 ms |
9332 KB |
Output is correct |
19 |
Correct |
214 ms |
15428 KB |
Output is correct |
20 |
Correct |
670 ms |
32068 KB |
Output is correct |
21 |
Correct |
335 ms |
19660 KB |
Output is correct |
22 |
Correct |
282 ms |
14336 KB |
Output is correct |
23 |
Correct |
672 ms |
32052 KB |
Output is correct |
24 |
Correct |
680 ms |
32132 KB |
Output is correct |
25 |
Correct |
569 ms |
32196 KB |
Output is correct |
26 |
Correct |
229 ms |
15036 KB |
Output is correct |
27 |
Correct |
213 ms |
15296 KB |
Output is correct |
28 |
Correct |
282 ms |
15036 KB |
Output is correct |
29 |
Correct |
213 ms |
15168 KB |
Output is correct |
30 |
Correct |
220 ms |
15428 KB |
Output is correct |
31 |
Correct |
2 ms |
7000 KB |
Output is correct |
32 |
Correct |
2 ms |
7004 KB |
Output is correct |
33 |
Correct |
2 ms |
7140 KB |
Output is correct |
34 |
Correct |
2 ms |
7004 KB |
Output is correct |
35 |
Correct |
2 ms |
7000 KB |
Output is correct |
36 |
Correct |
2 ms |
7004 KB |
Output is correct |
37 |
Correct |
2 ms |
7004 KB |
Output is correct |
38 |
Correct |
2 ms |
7004 KB |
Output is correct |
39 |
Correct |
2 ms |
7004 KB |
Output is correct |
40 |
Correct |
2 ms |
7004 KB |
Output is correct |
41 |
Correct |
149 ms |
17456 KB |
Output is correct |
42 |
Correct |
341 ms |
30408 KB |
Output is correct |
43 |
Correct |
339 ms |
30412 KB |
Output is correct |
44 |
Correct |
62 ms |
11860 KB |
Output is correct |
45 |
Correct |
414 ms |
30404 KB |
Output is correct |
46 |
Correct |
271 ms |
30392 KB |
Output is correct |
47 |
Correct |
286 ms |
30404 KB |
Output is correct |
48 |
Correct |
275 ms |
30464 KB |
Output is correct |
49 |
Correct |
280 ms |
30412 KB |
Output is correct |
50 |
Correct |
444 ms |
30572 KB |
Output is correct |
51 |
Correct |
421 ms |
30416 KB |
Output is correct |
52 |
Correct |
377 ms |
30512 KB |
Output is correct |
53 |
Correct |
341 ms |
30412 KB |
Output is correct |
54 |
Correct |
284 ms |
30452 KB |
Output is correct |
55 |
Correct |
379 ms |
30664 KB |
Output is correct |
56 |
Correct |
342 ms |
30412 KB |
Output is correct |
57 |
Correct |
289 ms |
30408 KB |
Output is correct |
58 |
Correct |
268 ms |
30412 KB |
Output is correct |
59 |
Correct |
41 ms |
11900 KB |
Output is correct |
60 |
Correct |
319 ms |
30432 KB |
Output is correct |
61 |
Correct |
273 ms |
31156 KB |
Output is correct |
62 |
Correct |
56 ms |
13640 KB |
Output is correct |
63 |
Correct |
95 ms |
12576 KB |
Output is correct |
64 |
Correct |
55 ms |
13636 KB |
Output is correct |
65 |
Correct |
56 ms |
13684 KB |
Output is correct |
66 |
Correct |
79 ms |
12624 KB |
Output is correct |
67 |
Correct |
67 ms |
11856 KB |
Output is correct |
68 |
Correct |
51 ms |
13636 KB |
Output is correct |
69 |
Correct |
64 ms |
11860 KB |
Output is correct |
70 |
Correct |
60 ms |
13616 KB |
Output is correct |
71 |
Correct |
65 ms |
11860 KB |
Output is correct |
72 |
Correct |
401 ms |
19156 KB |
Output is correct |
73 |
Correct |
712 ms |
32028 KB |
Output is correct |
74 |
Correct |
748 ms |
32232 KB |
Output is correct |
75 |
Correct |
690 ms |
32044 KB |
Output is correct |
76 |
Correct |
666 ms |
32204 KB |
Output is correct |
77 |
Correct |
675 ms |
32200 KB |
Output is correct |
78 |
Correct |
646 ms |
32108 KB |
Output is correct |
79 |
Correct |
697 ms |
32060 KB |
Output is correct |
80 |
Correct |
692 ms |
32120 KB |
Output is correct |
81 |
Correct |
691 ms |
31996 KB |
Output is correct |
82 |
Correct |
752 ms |
32112 KB |
Output is correct |
83 |
Correct |
638 ms |
32204 KB |
Output is correct |
84 |
Correct |
623 ms |
32204 KB |
Output is correct |
85 |
Correct |
555 ms |
32192 KB |
Output is correct |
86 |
Correct |
616 ms |
32092 KB |
Output is correct |
87 |
Correct |
654 ms |
32328 KB |
Output is correct |
88 |
Correct |
650 ms |
32096 KB |
Output is correct |
89 |
Correct |
272 ms |
14164 KB |
Output is correct |
90 |
Correct |
708 ms |
32072 KB |
Output is correct |
91 |
Correct |
388 ms |
32468 KB |
Output is correct |
92 |
Correct |
245 ms |
15168 KB |
Output is correct |
93 |
Correct |
308 ms |
14416 KB |
Output is correct |
94 |
Correct |
226 ms |
15160 KB |
Output is correct |
95 |
Correct |
220 ms |
15112 KB |
Output is correct |
96 |
Correct |
281 ms |
14028 KB |
Output is correct |
97 |
Correct |
291 ms |
13652 KB |
Output is correct |
98 |
Correct |
229 ms |
15128 KB |
Output is correct |
99 |
Correct |
250 ms |
13832 KB |
Output is correct |
100 |
Correct |
222 ms |
15176 KB |
Output is correct |