#ifndef LOCAL
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>
typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
/*
ll pw(ll a, ll b) {
ll ans = 1; while (b) {
while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
ans = (ans * a) % MOD, --b;
} return ans;
}
*/
const int MAXN = 220000;
const int LOG = 20;
const int INF = 2e9 + 10000;
int p[MAXN];
int sz[MAXN];
vector<pair<int, int> > eds[MAXN];
vector<int> eee[MAXN];
vector<tuple<int, int, int> > ed;
int dd[MAXN];
set<pair<int, int> > ss;
int fl[MAXN];
int tin[MAXN];
int tout[MAXN];
int tm1;
int up[LOG][MAXN];
int upp[LOG][MAXN];
int n, m;
int get(int a) {
if (p[a] == a)
return a;
return p[a] = get(p[a]);
}
int un(int a, int b) {
a = get(a);
b = get(b);
if (a == b)
return 0;
if (sz[a] > sz[b])
swap(a, b);
p[a] = b;
sz[b] += sz[a];
return 1;
}
void dfs1(int v, int p) {
tin[v] = tm1++;
up[0][v] = p;
upp[0][v] = min(dd[v], dd[p]);
for (int i = 1; i < LOG; ++i) {
up[i][v] = up[i - 1][up[i - 1][v]];
upp[i][v] = min(upp[i - 1][v], upp[i - 1][up[i - 1][v]]);
}
for (int u: eee[v]) {
if (u == p)
continue;
dfs1(u, v);
}
tout[v] = tm1;
}
int is_p(int a, int b) {
return (tin[a] <= tin[b] && tin[b] < tout[a]);
}
int lca(int a, int b) {
if (is_p(a, b))
return a;
if (is_p(b, a))
return b;
for (int i = LOG - 1; i >= 0; --i) {
if (!is_p(up[i][a], b))
a = up[i][a];
}
return up[0][a];
}
int gett(int a, int b) {
int ans = min(dd[a], dd[b]);
for (int i = LOG - 1; i >= 0; --i) {
if (is_p(b, up[i][a]))
ans = min(ans, upp[i][a]), a = up[i][a];
}
return ans;
}
int get(int a, int b) {
int x = lca(a, b);
return min(gett(a, x), gett(b, x));
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
--a, --b;
eds[a].push_back(make_pair(b, c));
eds[b].push_back(make_pair(a, c));
}
for (int i = 0; i < n; ++i)
dd[i] = INF;
int k;
scanf("%d", &k);
for (int i = 0; i < k; ++i) {
int x;
scanf("%d", &x);
--x;
fl[x] = 1;
dd[x] = 0;
ss.insert(make_pair(0, x));
}
while (!ss.empty()) {
int x = ss.begin()->second;
ss.erase(ss.begin());
for (auto e: eds[x]) {
int u = e.first;
if (dd[u] > dd[x] + e.second) {
ss.erase(make_pair(dd[u], u));
dd[u] = dd[x] + e.second;
ss.insert(make_pair(dd[u], u));
}
}
}
for (int i = 0; i < n; ++i)
p[i] = i, sz[i] = 1;
for (int i = 0; i < n; ++i) {
for (auto e: eds[i]) {
if (e.first > i)
ed.push_back(make_tuple(min(dd[i], dd[e.first]), i, e.first));
}
}
sort(ed.rbegin(), ed.rend());
for (int i = 0; i < ed.size(); ++i) {
int a, b, len;
tie(len, a, b) = ed[i];
if (un(a, b))
eee[a].push_back(b), eee[b].push_back(a);
}
dfs1(0, 0);
int q;
scanf("%d", &q);
for (int i = 0; i < q; ++i) {
int a, b;
scanf("%d%d", &a, &b);
--a, --b;
printf("%d\n", get(a, b));
}
return 0;
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:148:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ed.size(); ++i) {
~~^~~~~~~~~~~
plan.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
plan.cpp:110:8: 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:118:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
~~~~~^~~~~~~~~~
plan.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
plan.cpp:156:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
plan.cpp:159:8: 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 |
12 ms |
10872 KB |
Output is correct |
2 |
Correct |
14 ms |
11128 KB |
Output is correct |
3 |
Correct |
14 ms |
11128 KB |
Output is correct |
4 |
Correct |
12 ms |
10920 KB |
Output is correct |
5 |
Correct |
14 ms |
11256 KB |
Output is correct |
6 |
Correct |
14 ms |
11128 KB |
Output is correct |
7 |
Correct |
12 ms |
10972 KB |
Output is correct |
8 |
Correct |
12 ms |
11000 KB |
Output is correct |
9 |
Correct |
14 ms |
11128 KB |
Output is correct |
10 |
Correct |
14 ms |
11220 KB |
Output is correct |
11 |
Correct |
14 ms |
11128 KB |
Output is correct |
12 |
Correct |
13 ms |
11128 KB |
Output is correct |
13 |
Correct |
14 ms |
11128 KB |
Output is correct |
14 |
Correct |
14 ms |
11232 KB |
Output is correct |
15 |
Correct |
14 ms |
11152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
10872 KB |
Output is correct |
2 |
Correct |
14 ms |
11128 KB |
Output is correct |
3 |
Correct |
14 ms |
11128 KB |
Output is correct |
4 |
Correct |
12 ms |
10920 KB |
Output is correct |
5 |
Correct |
14 ms |
11256 KB |
Output is correct |
6 |
Correct |
14 ms |
11128 KB |
Output is correct |
7 |
Correct |
12 ms |
10972 KB |
Output is correct |
8 |
Correct |
12 ms |
11000 KB |
Output is correct |
9 |
Correct |
14 ms |
11128 KB |
Output is correct |
10 |
Correct |
14 ms |
11220 KB |
Output is correct |
11 |
Correct |
14 ms |
11128 KB |
Output is correct |
12 |
Correct |
13 ms |
11128 KB |
Output is correct |
13 |
Correct |
14 ms |
11128 KB |
Output is correct |
14 |
Correct |
14 ms |
11232 KB |
Output is correct |
15 |
Correct |
14 ms |
11152 KB |
Output is correct |
16 |
Correct |
321 ms |
33984 KB |
Output is correct |
17 |
Correct |
1034 ms |
53180 KB |
Output is correct |
18 |
Correct |
70 ms |
15900 KB |
Output is correct |
19 |
Correct |
278 ms |
38992 KB |
Output is correct |
20 |
Correct |
1252 ms |
53208 KB |
Output is correct |
21 |
Correct |
552 ms |
42184 KB |
Output is correct |
22 |
Correct |
313 ms |
41392 KB |
Output is correct |
23 |
Correct |
1002 ms |
52496 KB |
Output is correct |
24 |
Correct |
1064 ms |
52668 KB |
Output is correct |
25 |
Correct |
1042 ms |
52548 KB |
Output is correct |
26 |
Correct |
263 ms |
39296 KB |
Output is correct |
27 |
Correct |
253 ms |
38872 KB |
Output is correct |
28 |
Correct |
250 ms |
39436 KB |
Output is correct |
29 |
Correct |
246 ms |
38564 KB |
Output is correct |
30 |
Correct |
291 ms |
38608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
10876 KB |
Output is correct |
2 |
Correct |
12 ms |
11000 KB |
Output is correct |
3 |
Correct |
12 ms |
10876 KB |
Output is correct |
4 |
Correct |
13 ms |
10872 KB |
Output is correct |
5 |
Correct |
12 ms |
10872 KB |
Output is correct |
6 |
Correct |
13 ms |
10872 KB |
Output is correct |
7 |
Correct |
13 ms |
10872 KB |
Output is correct |
8 |
Correct |
12 ms |
10872 KB |
Output is correct |
9 |
Correct |
12 ms |
10872 KB |
Output is correct |
10 |
Correct |
12 ms |
10872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
437 ms |
40964 KB |
Output is correct |
2 |
Correct |
866 ms |
52216 KB |
Output is correct |
3 |
Correct |
839 ms |
51940 KB |
Output is correct |
4 |
Correct |
231 ms |
39020 KB |
Output is correct |
5 |
Correct |
909 ms |
52376 KB |
Output is correct |
6 |
Correct |
859 ms |
52456 KB |
Output is correct |
7 |
Correct |
821 ms |
52484 KB |
Output is correct |
8 |
Correct |
834 ms |
52804 KB |
Output is correct |
9 |
Correct |
865 ms |
52288 KB |
Output is correct |
10 |
Correct |
830 ms |
52320 KB |
Output is correct |
11 |
Correct |
857 ms |
52088 KB |
Output is correct |
12 |
Correct |
850 ms |
52948 KB |
Output is correct |
13 |
Correct |
877 ms |
52356 KB |
Output is correct |
14 |
Correct |
876 ms |
52948 KB |
Output is correct |
15 |
Correct |
884 ms |
53048 KB |
Output is correct |
16 |
Correct |
917 ms |
52900 KB |
Output is correct |
17 |
Correct |
1082 ms |
53184 KB |
Output is correct |
18 |
Correct |
1012 ms |
53012 KB |
Output is correct |
19 |
Correct |
245 ms |
39844 KB |
Output is correct |
20 |
Correct |
844 ms |
52752 KB |
Output is correct |
21 |
Correct |
745 ms |
52088 KB |
Output is correct |
22 |
Correct |
175 ms |
38132 KB |
Output is correct |
23 |
Correct |
239 ms |
37532 KB |
Output is correct |
24 |
Correct |
220 ms |
38072 KB |
Output is correct |
25 |
Correct |
177 ms |
37292 KB |
Output is correct |
26 |
Correct |
253 ms |
37496 KB |
Output is correct |
27 |
Correct |
224 ms |
39164 KB |
Output is correct |
28 |
Correct |
176 ms |
37576 KB |
Output is correct |
29 |
Correct |
231 ms |
38496 KB |
Output is correct |
30 |
Correct |
167 ms |
37524 KB |
Output is correct |
31 |
Correct |
224 ms |
38464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
10872 KB |
Output is correct |
2 |
Correct |
14 ms |
11128 KB |
Output is correct |
3 |
Correct |
14 ms |
11128 KB |
Output is correct |
4 |
Correct |
12 ms |
10920 KB |
Output is correct |
5 |
Correct |
14 ms |
11256 KB |
Output is correct |
6 |
Correct |
14 ms |
11128 KB |
Output is correct |
7 |
Correct |
12 ms |
10972 KB |
Output is correct |
8 |
Correct |
12 ms |
11000 KB |
Output is correct |
9 |
Correct |
14 ms |
11128 KB |
Output is correct |
10 |
Correct |
14 ms |
11220 KB |
Output is correct |
11 |
Correct |
14 ms |
11128 KB |
Output is correct |
12 |
Correct |
13 ms |
11128 KB |
Output is correct |
13 |
Correct |
14 ms |
11128 KB |
Output is correct |
14 |
Correct |
14 ms |
11232 KB |
Output is correct |
15 |
Correct |
14 ms |
11152 KB |
Output is correct |
16 |
Correct |
321 ms |
33984 KB |
Output is correct |
17 |
Correct |
1034 ms |
53180 KB |
Output is correct |
18 |
Correct |
70 ms |
15900 KB |
Output is correct |
19 |
Correct |
278 ms |
38992 KB |
Output is correct |
20 |
Correct |
1252 ms |
53208 KB |
Output is correct |
21 |
Correct |
552 ms |
42184 KB |
Output is correct |
22 |
Correct |
313 ms |
41392 KB |
Output is correct |
23 |
Correct |
1002 ms |
52496 KB |
Output is correct |
24 |
Correct |
1064 ms |
52668 KB |
Output is correct |
25 |
Correct |
1042 ms |
52548 KB |
Output is correct |
26 |
Correct |
263 ms |
39296 KB |
Output is correct |
27 |
Correct |
253 ms |
38872 KB |
Output is correct |
28 |
Correct |
250 ms |
39436 KB |
Output is correct |
29 |
Correct |
246 ms |
38564 KB |
Output is correct |
30 |
Correct |
291 ms |
38608 KB |
Output is correct |
31 |
Correct |
15 ms |
10876 KB |
Output is correct |
32 |
Correct |
12 ms |
11000 KB |
Output is correct |
33 |
Correct |
12 ms |
10876 KB |
Output is correct |
34 |
Correct |
13 ms |
10872 KB |
Output is correct |
35 |
Correct |
12 ms |
10872 KB |
Output is correct |
36 |
Correct |
13 ms |
10872 KB |
Output is correct |
37 |
Correct |
13 ms |
10872 KB |
Output is correct |
38 |
Correct |
12 ms |
10872 KB |
Output is correct |
39 |
Correct |
12 ms |
10872 KB |
Output is correct |
40 |
Correct |
12 ms |
10872 KB |
Output is correct |
41 |
Correct |
437 ms |
40964 KB |
Output is correct |
42 |
Correct |
866 ms |
52216 KB |
Output is correct |
43 |
Correct |
839 ms |
51940 KB |
Output is correct |
44 |
Correct |
231 ms |
39020 KB |
Output is correct |
45 |
Correct |
909 ms |
52376 KB |
Output is correct |
46 |
Correct |
859 ms |
52456 KB |
Output is correct |
47 |
Correct |
821 ms |
52484 KB |
Output is correct |
48 |
Correct |
834 ms |
52804 KB |
Output is correct |
49 |
Correct |
865 ms |
52288 KB |
Output is correct |
50 |
Correct |
830 ms |
52320 KB |
Output is correct |
51 |
Correct |
857 ms |
52088 KB |
Output is correct |
52 |
Correct |
850 ms |
52948 KB |
Output is correct |
53 |
Correct |
877 ms |
52356 KB |
Output is correct |
54 |
Correct |
876 ms |
52948 KB |
Output is correct |
55 |
Correct |
884 ms |
53048 KB |
Output is correct |
56 |
Correct |
917 ms |
52900 KB |
Output is correct |
57 |
Correct |
1082 ms |
53184 KB |
Output is correct |
58 |
Correct |
1012 ms |
53012 KB |
Output is correct |
59 |
Correct |
245 ms |
39844 KB |
Output is correct |
60 |
Correct |
844 ms |
52752 KB |
Output is correct |
61 |
Correct |
745 ms |
52088 KB |
Output is correct |
62 |
Correct |
175 ms |
38132 KB |
Output is correct |
63 |
Correct |
239 ms |
37532 KB |
Output is correct |
64 |
Correct |
220 ms |
38072 KB |
Output is correct |
65 |
Correct |
177 ms |
37292 KB |
Output is correct |
66 |
Correct |
253 ms |
37496 KB |
Output is correct |
67 |
Correct |
224 ms |
39164 KB |
Output is correct |
68 |
Correct |
176 ms |
37576 KB |
Output is correct |
69 |
Correct |
231 ms |
38496 KB |
Output is correct |
70 |
Correct |
167 ms |
37524 KB |
Output is correct |
71 |
Correct |
224 ms |
38464 KB |
Output is correct |
72 |
Correct |
630 ms |
41244 KB |
Output is correct |
73 |
Correct |
1008 ms |
52324 KB |
Output is correct |
74 |
Correct |
1006 ms |
52896 KB |
Output is correct |
75 |
Correct |
1054 ms |
53668 KB |
Output is correct |
76 |
Correct |
1094 ms |
54960 KB |
Output is correct |
77 |
Correct |
1177 ms |
55204 KB |
Output is correct |
78 |
Correct |
1051 ms |
55164 KB |
Output is correct |
79 |
Correct |
1030 ms |
54904 KB |
Output is correct |
80 |
Correct |
1077 ms |
53008 KB |
Output is correct |
81 |
Correct |
1041 ms |
54164 KB |
Output is correct |
82 |
Correct |
1020 ms |
54480 KB |
Output is correct |
83 |
Correct |
1047 ms |
52716 KB |
Output is correct |
84 |
Correct |
1061 ms |
52888 KB |
Output is correct |
85 |
Correct |
992 ms |
54296 KB |
Output is correct |
86 |
Correct |
968 ms |
54852 KB |
Output is correct |
87 |
Correct |
1010 ms |
54280 KB |
Output is correct |
88 |
Correct |
1051 ms |
54500 KB |
Output is correct |
89 |
Correct |
404 ms |
41420 KB |
Output is correct |
90 |
Correct |
1051 ms |
55032 KB |
Output is correct |
91 |
Correct |
904 ms |
55440 KB |
Output is correct |
92 |
Correct |
365 ms |
39360 KB |
Output is correct |
93 |
Correct |
536 ms |
38808 KB |
Output is correct |
94 |
Correct |
345 ms |
39992 KB |
Output is correct |
95 |
Correct |
350 ms |
39832 KB |
Output is correct |
96 |
Correct |
437 ms |
39376 KB |
Output is correct |
97 |
Correct |
375 ms |
40704 KB |
Output is correct |
98 |
Correct |
331 ms |
40644 KB |
Output is correct |
99 |
Correct |
467 ms |
41760 KB |
Output is correct |
100 |
Correct |
333 ms |
40092 KB |
Output is correct |