#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 1e5+5;
int n, m, k, q, d[N], dsu[N];
vector<pii> g[N];
vector<int> t[N];
priority_queue<pii, vector<pii>, greater<pii> > Q;
int find(int x) { return dsu[x] = x == dsu[x] ? x : find(dsu[x]); }
int dep[N], par[N][18];
void dfs(int u, int p) {
dep[u] = dep[p] + 1, par[u][0] = p;
for(int i = 1; i <= 17; i++) par[u][i] = par[par[u][i-1]][i-1];
for(int v : t[u]) if(v != p) dfs(v, u);
}
int lca(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
for(int i = 17; ~i; i--) if(dep[par[a][i]] >= dep[b]) a = par[a][i];
if(a == b) return a;
for(int i = 17; ~i; i--) if(par[a][i] != par[b][i]) a = par[a][i], b = par[b][i];
return par[a][0];
}
int main() {
fill_n(d, N, 1e9), iota(dsu, dsu + N, 0);
scanf("%d %d", &n, &m);
for(int i = 1, a, b, c; i <= m; i++) {
scanf("%d %d %d", &a, &b, &c);
g[a].emplace_back(b, c);
g[b].emplace_back(a, c);
}
scanf("%d", &k);
for(int i = 1, a; i <= k; i++) {
scanf("%d", &a);
Q.emplace(d[a] = 0, a);
}
while(!Q.empty()) {
pii u = Q.top(); Q.pop();
if(d[u.y] != u.x) continue;
for(pii v : g[u.y]) if(u.x + v.y < d[v.x])
Q.emplace(d[v.x] = u.x + v.y, v.x);
}
vector<int> vec;
for(int i = 1; i <= n; i++) vec.emplace_back(i);
sort(vec.begin(), vec.end(), [&](int a, int b) {
return pii(d[a], a) > pii(d[b], b);
});
for(int u : vec) for(pii v : g[u]) if(pii(d[v.x], v.x) > pii(d[u], u)) {
int pv = find(v.x);
if(pv == u) continue;
t[u].emplace_back(pv), t[pv].emplace_back(u);
dsu[pv] = u;
}
dfs(vec.back(), 0);
scanf("%d", &q);
for(int i = 1, a, b; i <= q; i++) {
scanf("%d %d", &a, &b);
printf("%d\n", d[lca(a, b)]);
}
return 0;
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
~~~~~^~~~~~~~~~
plan.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a);
~~~~~^~~~~~~~~~
plan.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
plan.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5760 KB |
Output is correct |
2 |
Correct |
10 ms |
6016 KB |
Output is correct |
3 |
Correct |
10 ms |
6016 KB |
Output is correct |
4 |
Correct |
8 ms |
5868 KB |
Output is correct |
5 |
Correct |
9 ms |
6016 KB |
Output is correct |
6 |
Correct |
9 ms |
6016 KB |
Output is correct |
7 |
Correct |
9 ms |
5760 KB |
Output is correct |
8 |
Correct |
8 ms |
5760 KB |
Output is correct |
9 |
Correct |
10 ms |
6016 KB |
Output is correct |
10 |
Correct |
10 ms |
6016 KB |
Output is correct |
11 |
Correct |
11 ms |
6016 KB |
Output is correct |
12 |
Correct |
10 ms |
6016 KB |
Output is correct |
13 |
Correct |
10 ms |
6016 KB |
Output is correct |
14 |
Correct |
10 ms |
6016 KB |
Output is correct |
15 |
Correct |
10 ms |
6016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5760 KB |
Output is correct |
2 |
Correct |
10 ms |
6016 KB |
Output is correct |
3 |
Correct |
10 ms |
6016 KB |
Output is correct |
4 |
Correct |
8 ms |
5868 KB |
Output is correct |
5 |
Correct |
9 ms |
6016 KB |
Output is correct |
6 |
Correct |
9 ms |
6016 KB |
Output is correct |
7 |
Correct |
9 ms |
5760 KB |
Output is correct |
8 |
Correct |
8 ms |
5760 KB |
Output is correct |
9 |
Correct |
10 ms |
6016 KB |
Output is correct |
10 |
Correct |
10 ms |
6016 KB |
Output is correct |
11 |
Correct |
11 ms |
6016 KB |
Output is correct |
12 |
Correct |
10 ms |
6016 KB |
Output is correct |
13 |
Correct |
10 ms |
6016 KB |
Output is correct |
14 |
Correct |
10 ms |
6016 KB |
Output is correct |
15 |
Correct |
10 ms |
6016 KB |
Output is correct |
16 |
Correct |
298 ms |
22512 KB |
Output is correct |
17 |
Correct |
843 ms |
44336 KB |
Output is correct |
18 |
Correct |
55 ms |
9720 KB |
Output is correct |
19 |
Correct |
203 ms |
25144 KB |
Output is correct |
20 |
Correct |
809 ms |
44216 KB |
Output is correct |
21 |
Correct |
418 ms |
30996 KB |
Output is correct |
22 |
Correct |
233 ms |
28408 KB |
Output is correct |
23 |
Correct |
775 ms |
44396 KB |
Output is correct |
24 |
Correct |
782 ms |
44184 KB |
Output is correct |
25 |
Correct |
811 ms |
44396 KB |
Output is correct |
26 |
Correct |
225 ms |
25064 KB |
Output is correct |
27 |
Correct |
238 ms |
25192 KB |
Output is correct |
28 |
Correct |
216 ms |
24968 KB |
Output is correct |
29 |
Correct |
214 ms |
25064 KB |
Output is correct |
30 |
Correct |
237 ms |
25188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5760 KB |
Output is correct |
2 |
Correct |
9 ms |
5760 KB |
Output is correct |
3 |
Correct |
9 ms |
5888 KB |
Output is correct |
4 |
Correct |
8 ms |
5760 KB |
Output is correct |
5 |
Correct |
8 ms |
5760 KB |
Output is correct |
6 |
Correct |
8 ms |
5760 KB |
Output is correct |
7 |
Correct |
9 ms |
5760 KB |
Output is correct |
8 |
Correct |
8 ms |
5888 KB |
Output is correct |
9 |
Correct |
8 ms |
5888 KB |
Output is correct |
10 |
Correct |
8 ms |
5760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
312 ms |
28912 KB |
Output is correct |
2 |
Correct |
659 ms |
42524 KB |
Output is correct |
3 |
Correct |
646 ms |
42472 KB |
Output is correct |
4 |
Correct |
165 ms |
23924 KB |
Output is correct |
5 |
Correct |
671 ms |
42528 KB |
Output is correct |
6 |
Correct |
718 ms |
42472 KB |
Output is correct |
7 |
Correct |
676 ms |
42604 KB |
Output is correct |
8 |
Correct |
654 ms |
42476 KB |
Output is correct |
9 |
Correct |
675 ms |
42476 KB |
Output is correct |
10 |
Correct |
657 ms |
42476 KB |
Output is correct |
11 |
Correct |
612 ms |
42604 KB |
Output is correct |
12 |
Correct |
611 ms |
42476 KB |
Output is correct |
13 |
Correct |
636 ms |
42480 KB |
Output is correct |
14 |
Correct |
659 ms |
42604 KB |
Output is correct |
15 |
Correct |
600 ms |
42596 KB |
Output is correct |
16 |
Correct |
651 ms |
42348 KB |
Output is correct |
17 |
Correct |
651 ms |
42480 KB |
Output is correct |
18 |
Correct |
601 ms |
42484 KB |
Output is correct |
19 |
Correct |
163 ms |
26228 KB |
Output is correct |
20 |
Correct |
644 ms |
42576 KB |
Output is correct |
21 |
Correct |
575 ms |
42612 KB |
Output is correct |
22 |
Correct |
141 ms |
23528 KB |
Output is correct |
23 |
Correct |
160 ms |
23044 KB |
Output is correct |
24 |
Correct |
161 ms |
23524 KB |
Output is correct |
25 |
Correct |
161 ms |
23532 KB |
Output is correct |
26 |
Correct |
223 ms |
22384 KB |
Output is correct |
27 |
Correct |
152 ms |
23800 KB |
Output is correct |
28 |
Correct |
155 ms |
23636 KB |
Output is correct |
29 |
Correct |
148 ms |
23920 KB |
Output is correct |
30 |
Correct |
148 ms |
23492 KB |
Output is correct |
31 |
Correct |
157 ms |
23896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5760 KB |
Output is correct |
2 |
Correct |
10 ms |
6016 KB |
Output is correct |
3 |
Correct |
10 ms |
6016 KB |
Output is correct |
4 |
Correct |
8 ms |
5868 KB |
Output is correct |
5 |
Correct |
9 ms |
6016 KB |
Output is correct |
6 |
Correct |
9 ms |
6016 KB |
Output is correct |
7 |
Correct |
9 ms |
5760 KB |
Output is correct |
8 |
Correct |
8 ms |
5760 KB |
Output is correct |
9 |
Correct |
10 ms |
6016 KB |
Output is correct |
10 |
Correct |
10 ms |
6016 KB |
Output is correct |
11 |
Correct |
11 ms |
6016 KB |
Output is correct |
12 |
Correct |
10 ms |
6016 KB |
Output is correct |
13 |
Correct |
10 ms |
6016 KB |
Output is correct |
14 |
Correct |
10 ms |
6016 KB |
Output is correct |
15 |
Correct |
10 ms |
6016 KB |
Output is correct |
16 |
Correct |
298 ms |
22512 KB |
Output is correct |
17 |
Correct |
843 ms |
44336 KB |
Output is correct |
18 |
Correct |
55 ms |
9720 KB |
Output is correct |
19 |
Correct |
203 ms |
25144 KB |
Output is correct |
20 |
Correct |
809 ms |
44216 KB |
Output is correct |
21 |
Correct |
418 ms |
30996 KB |
Output is correct |
22 |
Correct |
233 ms |
28408 KB |
Output is correct |
23 |
Correct |
775 ms |
44396 KB |
Output is correct |
24 |
Correct |
782 ms |
44184 KB |
Output is correct |
25 |
Correct |
811 ms |
44396 KB |
Output is correct |
26 |
Correct |
225 ms |
25064 KB |
Output is correct |
27 |
Correct |
238 ms |
25192 KB |
Output is correct |
28 |
Correct |
216 ms |
24968 KB |
Output is correct |
29 |
Correct |
214 ms |
25064 KB |
Output is correct |
30 |
Correct |
237 ms |
25188 KB |
Output is correct |
31 |
Correct |
8 ms |
5760 KB |
Output is correct |
32 |
Correct |
9 ms |
5760 KB |
Output is correct |
33 |
Correct |
9 ms |
5888 KB |
Output is correct |
34 |
Correct |
8 ms |
5760 KB |
Output is correct |
35 |
Correct |
8 ms |
5760 KB |
Output is correct |
36 |
Correct |
8 ms |
5760 KB |
Output is correct |
37 |
Correct |
9 ms |
5760 KB |
Output is correct |
38 |
Correct |
8 ms |
5888 KB |
Output is correct |
39 |
Correct |
8 ms |
5888 KB |
Output is correct |
40 |
Correct |
8 ms |
5760 KB |
Output is correct |
41 |
Correct |
312 ms |
28912 KB |
Output is correct |
42 |
Correct |
659 ms |
42524 KB |
Output is correct |
43 |
Correct |
646 ms |
42472 KB |
Output is correct |
44 |
Correct |
165 ms |
23924 KB |
Output is correct |
45 |
Correct |
671 ms |
42528 KB |
Output is correct |
46 |
Correct |
718 ms |
42472 KB |
Output is correct |
47 |
Correct |
676 ms |
42604 KB |
Output is correct |
48 |
Correct |
654 ms |
42476 KB |
Output is correct |
49 |
Correct |
675 ms |
42476 KB |
Output is correct |
50 |
Correct |
657 ms |
42476 KB |
Output is correct |
51 |
Correct |
612 ms |
42604 KB |
Output is correct |
52 |
Correct |
611 ms |
42476 KB |
Output is correct |
53 |
Correct |
636 ms |
42480 KB |
Output is correct |
54 |
Correct |
659 ms |
42604 KB |
Output is correct |
55 |
Correct |
600 ms |
42596 KB |
Output is correct |
56 |
Correct |
651 ms |
42348 KB |
Output is correct |
57 |
Correct |
651 ms |
42480 KB |
Output is correct |
58 |
Correct |
601 ms |
42484 KB |
Output is correct |
59 |
Correct |
163 ms |
26228 KB |
Output is correct |
60 |
Correct |
644 ms |
42576 KB |
Output is correct |
61 |
Correct |
575 ms |
42612 KB |
Output is correct |
62 |
Correct |
141 ms |
23528 KB |
Output is correct |
63 |
Correct |
160 ms |
23044 KB |
Output is correct |
64 |
Correct |
161 ms |
23524 KB |
Output is correct |
65 |
Correct |
161 ms |
23532 KB |
Output is correct |
66 |
Correct |
223 ms |
22384 KB |
Output is correct |
67 |
Correct |
152 ms |
23800 KB |
Output is correct |
68 |
Correct |
155 ms |
23636 KB |
Output is correct |
69 |
Correct |
148 ms |
23920 KB |
Output is correct |
70 |
Correct |
148 ms |
23492 KB |
Output is correct |
71 |
Correct |
157 ms |
23896 KB |
Output is correct |
72 |
Correct |
469 ms |
30868 KB |
Output is correct |
73 |
Correct |
846 ms |
44152 KB |
Output is correct |
74 |
Correct |
853 ms |
44140 KB |
Output is correct |
75 |
Correct |
818 ms |
44172 KB |
Output is correct |
76 |
Correct |
922 ms |
44140 KB |
Output is correct |
77 |
Correct |
823 ms |
43992 KB |
Output is correct |
78 |
Correct |
832 ms |
44220 KB |
Output is correct |
79 |
Correct |
720 ms |
44000 KB |
Output is correct |
80 |
Correct |
756 ms |
44140 KB |
Output is correct |
81 |
Correct |
733 ms |
44180 KB |
Output is correct |
82 |
Correct |
737 ms |
44136 KB |
Output is correct |
83 |
Correct |
776 ms |
44140 KB |
Output is correct |
84 |
Correct |
721 ms |
44276 KB |
Output is correct |
85 |
Correct |
778 ms |
44132 KB |
Output is correct |
86 |
Correct |
740 ms |
44136 KB |
Output is correct |
87 |
Correct |
815 ms |
44116 KB |
Output is correct |
88 |
Correct |
752 ms |
44244 KB |
Output is correct |
89 |
Correct |
271 ms |
28532 KB |
Output is correct |
90 |
Correct |
686 ms |
44016 KB |
Output is correct |
91 |
Correct |
639 ms |
44140 KB |
Output is correct |
92 |
Correct |
206 ms |
25192 KB |
Output is correct |
93 |
Correct |
259 ms |
25096 KB |
Output is correct |
94 |
Correct |
199 ms |
24936 KB |
Output is correct |
95 |
Correct |
219 ms |
25164 KB |
Output is correct |
96 |
Correct |
254 ms |
23920 KB |
Output is correct |
97 |
Correct |
272 ms |
25716 KB |
Output is correct |
98 |
Correct |
209 ms |
25064 KB |
Output is correct |
99 |
Correct |
321 ms |
25712 KB |
Output is correct |
100 |
Correct |
200 ms |
25064 KB |
Output is correct |