#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
using namespace std;
const int N = 5e5 + 5, INF = 1e9 + 5;
int n, m;
vector < int > g[N], gg[N];
int mas[N];
priority_queue < pair < int, int > > Q;
int q;
int s[N], f[N], l[N], r[N], mid[N];
pair < int, int > P[N], PP[N];
bool F[N];
int p[N];
int parent (int x){
if (p[x] == x)
return x;
return p[x] = parent (p[x]);
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
while (m--){
int u, v, x;
cin>>u>>v>>x;
g[u].pb (v);
gg[u].pb (x);
g[v].pb (u);
gg[v].pb (x);
}
for (int i = 1; i <= n; i++)
mas[i] = INF;
cin>>m;
while (m--){
int x;
cin>>x;
mas[x] = 0;
Q.push ({-mas[x], x});
}
cin>>q;
for (int i = 1; i <= q; i++){
cin>>s[i]>>f[i];
l[i] = 1;
r[i] = n;
}
while (Q.size() > 0){
int k = Q.top().S;
Q.pop();
if (F[k])
continue;
F[k] = 1;
for (int i = 0; i < g[k].size(); i++){
int to = g[k][i];
if (mas[to] > mas[k] + gg[k][i]){
mas[to] = mas[k] + gg[k][i];
Q.push ({-mas[to], to});
}
}
}
for (int i = 1; i <= n; i++)
P[i] = {-mas[i], i};
sort (P + 1, P + n + 1);
for (int mtvleli = 0; mtvleli < 30; mtvleli++){
for (int i = 1; i <= q; i++){
mid[i] = (l[i] + r[i]) / 2;
PP[i] = {mid[i], i};
}
sort (PP + 1, PP + q + 1);
int I = 1;
for (int i = 1; i <= n; i++){
F[i] = 0;
p[i] = i;
}
for (int i = 1; i <= n; i++){
int u = P[i].S;
F[u] = 1;
for (int j = 0; j < g[u].size(); j++)
if (F[g[u][j]] == 1){
parent (g[u][j]);
p[p[g[u][j]]] = u;
}
for (; I <= q && PP[I].F == i; I++){
int k = PP[I].S;
int u = s[k], v = f[k];
parent(u);
parent(v);
if (p[u] == p[v])
r[k] = mid[k];
else
l[k] = mid[k] + 1;
}
}
}
for (int i = 1; i <= q; i++)
cout<<-P[l[i]].F<<endl;
return 0;
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:59:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[k].size(); i++){
~~^~~~~~~~~~~~~
plan.cpp:84:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[u].size(); j++)
~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23928 KB |
Output is correct |
2 |
Correct |
29 ms |
24056 KB |
Output is correct |
3 |
Correct |
29 ms |
24056 KB |
Output is correct |
4 |
Correct |
23 ms |
23928 KB |
Output is correct |
5 |
Correct |
29 ms |
24056 KB |
Output is correct |
6 |
Correct |
29 ms |
24056 KB |
Output is correct |
7 |
Correct |
24 ms |
23928 KB |
Output is correct |
8 |
Correct |
24 ms |
23928 KB |
Output is correct |
9 |
Correct |
31 ms |
23964 KB |
Output is correct |
10 |
Correct |
32 ms |
24028 KB |
Output is correct |
11 |
Correct |
31 ms |
24100 KB |
Output is correct |
12 |
Correct |
29 ms |
24056 KB |
Output is correct |
13 |
Correct |
31 ms |
24056 KB |
Output is correct |
14 |
Correct |
31 ms |
24056 KB |
Output is correct |
15 |
Correct |
31 ms |
23944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23928 KB |
Output is correct |
2 |
Correct |
29 ms |
24056 KB |
Output is correct |
3 |
Correct |
29 ms |
24056 KB |
Output is correct |
4 |
Correct |
23 ms |
23928 KB |
Output is correct |
5 |
Correct |
29 ms |
24056 KB |
Output is correct |
6 |
Correct |
29 ms |
24056 KB |
Output is correct |
7 |
Correct |
24 ms |
23928 KB |
Output is correct |
8 |
Correct |
24 ms |
23928 KB |
Output is correct |
9 |
Correct |
31 ms |
23964 KB |
Output is correct |
10 |
Correct |
32 ms |
24028 KB |
Output is correct |
11 |
Correct |
31 ms |
24100 KB |
Output is correct |
12 |
Correct |
29 ms |
24056 KB |
Output is correct |
13 |
Correct |
31 ms |
24056 KB |
Output is correct |
14 |
Correct |
31 ms |
24056 KB |
Output is correct |
15 |
Correct |
31 ms |
23944 KB |
Output is correct |
16 |
Correct |
1416 ms |
34228 KB |
Output is correct |
17 |
Correct |
3707 ms |
45752 KB |
Output is correct |
18 |
Correct |
217 ms |
26160 KB |
Output is correct |
19 |
Correct |
838 ms |
36704 KB |
Output is correct |
20 |
Correct |
3700 ms |
45604 KB |
Output is correct |
21 |
Correct |
2021 ms |
37832 KB |
Output is correct |
22 |
Correct |
1072 ms |
35696 KB |
Output is correct |
23 |
Correct |
3645 ms |
45476 KB |
Output is correct |
24 |
Correct |
3665 ms |
45520 KB |
Output is correct |
25 |
Correct |
3616 ms |
45488 KB |
Output is correct |
26 |
Correct |
886 ms |
36512 KB |
Output is correct |
27 |
Correct |
879 ms |
36700 KB |
Output is correct |
28 |
Correct |
916 ms |
36536 KB |
Output is correct |
29 |
Correct |
874 ms |
36628 KB |
Output is correct |
30 |
Correct |
781 ms |
36816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23928 KB |
Output is correct |
2 |
Correct |
29 ms |
23828 KB |
Output is correct |
3 |
Correct |
31 ms |
23932 KB |
Output is correct |
4 |
Correct |
24 ms |
23928 KB |
Output is correct |
5 |
Correct |
24 ms |
23836 KB |
Output is correct |
6 |
Correct |
24 ms |
23836 KB |
Output is correct |
7 |
Correct |
29 ms |
23928 KB |
Output is correct |
8 |
Correct |
29 ms |
23928 KB |
Output is correct |
9 |
Correct |
24 ms |
23928 KB |
Output is correct |
10 |
Correct |
24 ms |
23928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1384 ms |
34872 KB |
Output is correct |
2 |
Correct |
2829 ms |
42472 KB |
Output is correct |
3 |
Correct |
2870 ms |
42444 KB |
Output is correct |
4 |
Correct |
567 ms |
32568 KB |
Output is correct |
5 |
Correct |
2807 ms |
42428 KB |
Output is correct |
6 |
Correct |
2833 ms |
42444 KB |
Output is correct |
7 |
Correct |
2828 ms |
42436 KB |
Output is correct |
8 |
Correct |
2829 ms |
42444 KB |
Output is correct |
9 |
Correct |
2808 ms |
42460 KB |
Output is correct |
10 |
Correct |
2807 ms |
42440 KB |
Output is correct |
11 |
Correct |
2816 ms |
42468 KB |
Output is correct |
12 |
Correct |
2786 ms |
42460 KB |
Output is correct |
13 |
Correct |
2861 ms |
42500 KB |
Output is correct |
14 |
Correct |
2805 ms |
42476 KB |
Output is correct |
15 |
Correct |
2835 ms |
42488 KB |
Output is correct |
16 |
Correct |
2861 ms |
42468 KB |
Output is correct |
17 |
Correct |
2806 ms |
42456 KB |
Output is correct |
18 |
Correct |
2823 ms |
42432 KB |
Output is correct |
19 |
Correct |
331 ms |
32648 KB |
Output is correct |
20 |
Correct |
2771 ms |
42428 KB |
Output is correct |
21 |
Correct |
2359 ms |
42208 KB |
Output is correct |
22 |
Correct |
279 ms |
33576 KB |
Output is correct |
23 |
Correct |
376 ms |
32080 KB |
Output is correct |
24 |
Correct |
306 ms |
33576 KB |
Output is correct |
25 |
Correct |
286 ms |
33480 KB |
Output is correct |
26 |
Correct |
465 ms |
32288 KB |
Output is correct |
27 |
Correct |
582 ms |
32648 KB |
Output is correct |
28 |
Correct |
286 ms |
33580 KB |
Output is correct |
29 |
Correct |
557 ms |
32576 KB |
Output is correct |
30 |
Correct |
275 ms |
33636 KB |
Output is correct |
31 |
Correct |
608 ms |
32716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23928 KB |
Output is correct |
2 |
Correct |
29 ms |
24056 KB |
Output is correct |
3 |
Correct |
29 ms |
24056 KB |
Output is correct |
4 |
Correct |
23 ms |
23928 KB |
Output is correct |
5 |
Correct |
29 ms |
24056 KB |
Output is correct |
6 |
Correct |
29 ms |
24056 KB |
Output is correct |
7 |
Correct |
24 ms |
23928 KB |
Output is correct |
8 |
Correct |
24 ms |
23928 KB |
Output is correct |
9 |
Correct |
31 ms |
23964 KB |
Output is correct |
10 |
Correct |
32 ms |
24028 KB |
Output is correct |
11 |
Correct |
31 ms |
24100 KB |
Output is correct |
12 |
Correct |
29 ms |
24056 KB |
Output is correct |
13 |
Correct |
31 ms |
24056 KB |
Output is correct |
14 |
Correct |
31 ms |
24056 KB |
Output is correct |
15 |
Correct |
31 ms |
23944 KB |
Output is correct |
16 |
Correct |
1416 ms |
34228 KB |
Output is correct |
17 |
Correct |
3707 ms |
45752 KB |
Output is correct |
18 |
Correct |
217 ms |
26160 KB |
Output is correct |
19 |
Correct |
838 ms |
36704 KB |
Output is correct |
20 |
Correct |
3700 ms |
45604 KB |
Output is correct |
21 |
Correct |
2021 ms |
37832 KB |
Output is correct |
22 |
Correct |
1072 ms |
35696 KB |
Output is correct |
23 |
Correct |
3645 ms |
45476 KB |
Output is correct |
24 |
Correct |
3665 ms |
45520 KB |
Output is correct |
25 |
Correct |
3616 ms |
45488 KB |
Output is correct |
26 |
Correct |
886 ms |
36512 KB |
Output is correct |
27 |
Correct |
879 ms |
36700 KB |
Output is correct |
28 |
Correct |
916 ms |
36536 KB |
Output is correct |
29 |
Correct |
874 ms |
36628 KB |
Output is correct |
30 |
Correct |
781 ms |
36816 KB |
Output is correct |
31 |
Correct |
24 ms |
23928 KB |
Output is correct |
32 |
Correct |
29 ms |
23828 KB |
Output is correct |
33 |
Correct |
31 ms |
23932 KB |
Output is correct |
34 |
Correct |
24 ms |
23928 KB |
Output is correct |
35 |
Correct |
24 ms |
23836 KB |
Output is correct |
36 |
Correct |
24 ms |
23836 KB |
Output is correct |
37 |
Correct |
29 ms |
23928 KB |
Output is correct |
38 |
Correct |
29 ms |
23928 KB |
Output is correct |
39 |
Correct |
24 ms |
23928 KB |
Output is correct |
40 |
Correct |
24 ms |
23928 KB |
Output is correct |
41 |
Correct |
1384 ms |
34872 KB |
Output is correct |
42 |
Correct |
2829 ms |
42472 KB |
Output is correct |
43 |
Correct |
2870 ms |
42444 KB |
Output is correct |
44 |
Correct |
567 ms |
32568 KB |
Output is correct |
45 |
Correct |
2807 ms |
42428 KB |
Output is correct |
46 |
Correct |
2833 ms |
42444 KB |
Output is correct |
47 |
Correct |
2828 ms |
42436 KB |
Output is correct |
48 |
Correct |
2829 ms |
42444 KB |
Output is correct |
49 |
Correct |
2808 ms |
42460 KB |
Output is correct |
50 |
Correct |
2807 ms |
42440 KB |
Output is correct |
51 |
Correct |
2816 ms |
42468 KB |
Output is correct |
52 |
Correct |
2786 ms |
42460 KB |
Output is correct |
53 |
Correct |
2861 ms |
42500 KB |
Output is correct |
54 |
Correct |
2805 ms |
42476 KB |
Output is correct |
55 |
Correct |
2835 ms |
42488 KB |
Output is correct |
56 |
Correct |
2861 ms |
42468 KB |
Output is correct |
57 |
Correct |
2806 ms |
42456 KB |
Output is correct |
58 |
Correct |
2823 ms |
42432 KB |
Output is correct |
59 |
Correct |
331 ms |
32648 KB |
Output is correct |
60 |
Correct |
2771 ms |
42428 KB |
Output is correct |
61 |
Correct |
2359 ms |
42208 KB |
Output is correct |
62 |
Correct |
279 ms |
33576 KB |
Output is correct |
63 |
Correct |
376 ms |
32080 KB |
Output is correct |
64 |
Correct |
306 ms |
33576 KB |
Output is correct |
65 |
Correct |
286 ms |
33480 KB |
Output is correct |
66 |
Correct |
465 ms |
32288 KB |
Output is correct |
67 |
Correct |
582 ms |
32648 KB |
Output is correct |
68 |
Correct |
286 ms |
33580 KB |
Output is correct |
69 |
Correct |
557 ms |
32576 KB |
Output is correct |
70 |
Correct |
275 ms |
33636 KB |
Output is correct |
71 |
Correct |
608 ms |
32716 KB |
Output is correct |
72 |
Correct |
2383 ms |
38212 KB |
Output is correct |
73 |
Correct |
3724 ms |
45552 KB |
Output is correct |
74 |
Correct |
3675 ms |
45696 KB |
Output is correct |
75 |
Correct |
3779 ms |
45560 KB |
Output is correct |
76 |
Correct |
3706 ms |
45576 KB |
Output is correct |
77 |
Correct |
3793 ms |
45580 KB |
Output is correct |
78 |
Correct |
3741 ms |
45564 KB |
Output is correct |
79 |
Correct |
3823 ms |
45628 KB |
Output is correct |
80 |
Correct |
3791 ms |
45696 KB |
Output is correct |
81 |
Correct |
3762 ms |
45684 KB |
Output is correct |
82 |
Correct |
3768 ms |
45680 KB |
Output is correct |
83 |
Correct |
3738 ms |
45816 KB |
Output is correct |
84 |
Correct |
3732 ms |
45572 KB |
Output is correct |
85 |
Correct |
3681 ms |
45512 KB |
Output is correct |
86 |
Correct |
3711 ms |
45572 KB |
Output is correct |
87 |
Correct |
3703 ms |
45704 KB |
Output is correct |
88 |
Correct |
3720 ms |
45636 KB |
Output is correct |
89 |
Correct |
1414 ms |
36300 KB |
Output is correct |
90 |
Correct |
3739 ms |
45716 KB |
Output is correct |
91 |
Correct |
3211 ms |
45152 KB |
Output is correct |
92 |
Correct |
841 ms |
36628 KB |
Output is correct |
93 |
Correct |
1285 ms |
35556 KB |
Output is correct |
94 |
Correct |
819 ms |
36452 KB |
Output is correct |
95 |
Correct |
868 ms |
36580 KB |
Output is correct |
96 |
Correct |
1178 ms |
35280 KB |
Output is correct |
97 |
Correct |
1464 ms |
35576 KB |
Output is correct |
98 |
Correct |
793 ms |
36576 KB |
Output is correct |
99 |
Correct |
1431 ms |
35460 KB |
Output is correct |
100 |
Correct |
928 ms |
36588 KB |
Output is correct |