#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
typedef long long ll;
ll linf = 1e15+1;
inline void scoobydoobydoo(){
ios::sync_with_stdio(false);
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
}
int n, m;
const int MAXN = 1e5+1; //M <= 5e5+1 dock
vector<pair<int, int> > adj[MAXN];
int weight[MAXN];
vector<int> edgesMST[MAXN];
int binPar[MAXN][20];
int binWeight[MAXN][20];
bool isVisited[MAXN];
bool active[MAXN];
int depth[MAXN];
void initBin(){
for (int j = 1; j < 20; j++){
for (int i = 0; i < n; i++){
binPar[i][j] = binPar[binPar[i][j-1]][j-1];
binWeight[i][j] = min(binWeight[i][j-1], binWeight[binPar[i][j-1]][j-1]);
}
}
}
int jump(int x, int k){
for (int i = 19; i >= 0; i--){
if (k&(1<<i))x = binPar[x][i];
}
return x;
}
int lca(int a, int b){
if (depth[a] < depth[b])swap(a, b);
a = jump(a, depth[a]-depth[b]);
if (a == b)return a;
for (int i = 19; i >= 0; i--){
int aT = binPar[a][i], bT = binPar[b][i];
if (aT != bT){
a = aT;
b = bT;
}
}
return binPar[a][0];
}
int getMin(int node, int k){
int mini = weight[node];
for (int i = 19; i >= 0; i--){
if (k&(1<<i)){
mini = min(mini, binWeight[node][i]);
node = binPar[node][i];
//cout << "; " << i << " " << binWeight[node][i] << endl;
}
}
return mini;
}
int main(){
scoobydoobydoo();
cin >> n >> m;
for (int i = 0; i < m; i++){
int a, b, w; cin >> a >> b >> w;
a--; b--;
adj[a].push_back({b, w});
adj[b].push_back({a, w});
}
int k; cin >> k;
vector<int> NPP(k);
priority_queue<pair<int, int> > pq;
for (int i = 0; i < k; i++){
cin >> NPP[i];
pq.push({0, --NPP[i]});
}
int maxi = -1;
int best;
while (!pq.empty()){
int node = pq.top().second;
int w = -pq.top().first;
pq.pop();
if (isVisited[node])continue;
isVisited[node] = true;
weight[node] = w;
if (weight[node] > maxi){
maxi = w;
best = node;
}
for (auto p : adj[node]){
if (!isVisited[p.first])pq.push({-(w+p.second), p.first});
}
}
active[best] = true;
priority_queue<vector<int> > sPq;
for (auto p : adj[best]){
sPq.push({weight[best], p.first, best, 1});
}
depth[best] = 0;
binPar[best][0] = best;
while (!sPq.empty()){
int node = sPq.top()[1];
int w = sPq.top()[0];
int pare = sPq.top()[2];
int dpt = sPq.top()[3];
sPq.pop();
if (active[node])continue;
active[node] = true;
binPar[node][0] = pare;
binWeight[node][0] = w;
depth[node] = dpt;
for (auto p : adj[node]){
if (!active[p.first])sPq.push({weight[node], p.first, node, dpt+1});
}
}
initBin();
vector<int> ans;
int q; cin >> q;
while (q--){
int s, t; cin >> s >> t;
s--; t--;
int LC = lca(s, t);
//cout << s << " " << t << " " << LC << endl;
//cout << getMin(s, depth[s]-depth[LC]) << " " << getMin(t, depth[t]-depth[LC]) << endl;
ans.push_back(min(getMin(s, depth[s]-depth[LC]), getMin(t, depth[t]-depth[LC])));
}
for (int x : ans){
cout << x << endl;
}
/*for (int i = 0; i < n; i++)cout << i << ": " << depth[i] << ", ";
cout << endl;
for (int i = 0; i < n; i++){
cout << i << ": " << endl << binPar[i][0] << " " << binPar[i][1] << " " << binPar[i][2] << endl;
cout << binWeight[i][0] << " " << binWeight[i][1] << " " << binWeight[i][2] << endl;
}*/
return 0;
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:131:21: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
131 | binPar[best][0] = best;
| ~~~~~~~~~~~~~~~~^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9308 KB |
Output is correct |
2 |
Correct |
4 ms |
9544 KB |
Output is correct |
3 |
Correct |
4 ms |
9308 KB |
Output is correct |
4 |
Correct |
2 ms |
9308 KB |
Output is correct |
5 |
Correct |
4 ms |
9560 KB |
Output is correct |
6 |
Correct |
4 ms |
9308 KB |
Output is correct |
7 |
Correct |
2 ms |
9308 KB |
Output is correct |
8 |
Correct |
2 ms |
9308 KB |
Output is correct |
9 |
Correct |
4 ms |
9308 KB |
Output is correct |
10 |
Correct |
4 ms |
9308 KB |
Output is correct |
11 |
Correct |
4 ms |
9308 KB |
Output is correct |
12 |
Correct |
5 ms |
9312 KB |
Output is correct |
13 |
Correct |
4 ms |
9304 KB |
Output is correct |
14 |
Correct |
3 ms |
9308 KB |
Output is correct |
15 |
Correct |
4 ms |
9476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9308 KB |
Output is correct |
2 |
Correct |
4 ms |
9544 KB |
Output is correct |
3 |
Correct |
4 ms |
9308 KB |
Output is correct |
4 |
Correct |
2 ms |
9308 KB |
Output is correct |
5 |
Correct |
4 ms |
9560 KB |
Output is correct |
6 |
Correct |
4 ms |
9308 KB |
Output is correct |
7 |
Correct |
2 ms |
9308 KB |
Output is correct |
8 |
Correct |
2 ms |
9308 KB |
Output is correct |
9 |
Correct |
4 ms |
9308 KB |
Output is correct |
10 |
Correct |
4 ms |
9308 KB |
Output is correct |
11 |
Correct |
4 ms |
9308 KB |
Output is correct |
12 |
Correct |
5 ms |
9312 KB |
Output is correct |
13 |
Correct |
4 ms |
9304 KB |
Output is correct |
14 |
Correct |
3 ms |
9308 KB |
Output is correct |
15 |
Correct |
4 ms |
9476 KB |
Output is correct |
16 |
Correct |
249 ms |
30584 KB |
Output is correct |
17 |
Correct |
761 ms |
68956 KB |
Output is correct |
18 |
Correct |
47 ms |
13896 KB |
Output is correct |
19 |
Correct |
230 ms |
35484 KB |
Output is correct |
20 |
Correct |
735 ms |
68860 KB |
Output is correct |
21 |
Correct |
372 ms |
39520 KB |
Output is correct |
22 |
Correct |
216 ms |
29132 KB |
Output is correct |
23 |
Correct |
682 ms |
69276 KB |
Output is correct |
24 |
Correct |
770 ms |
69044 KB |
Output is correct |
25 |
Correct |
749 ms |
68976 KB |
Output is correct |
26 |
Correct |
235 ms |
35236 KB |
Output is correct |
27 |
Correct |
263 ms |
35288 KB |
Output is correct |
28 |
Correct |
246 ms |
35504 KB |
Output is correct |
29 |
Correct |
235 ms |
35140 KB |
Output is correct |
30 |
Correct |
241 ms |
35804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9308 KB |
Output is correct |
2 |
Correct |
2 ms |
9276 KB |
Output is correct |
3 |
Correct |
2 ms |
9308 KB |
Output is correct |
4 |
Correct |
2 ms |
9308 KB |
Output is correct |
5 |
Correct |
2 ms |
9308 KB |
Output is correct |
6 |
Correct |
2 ms |
9308 KB |
Output is correct |
7 |
Correct |
2 ms |
9308 KB |
Output is correct |
8 |
Correct |
2 ms |
9304 KB |
Output is correct |
9 |
Correct |
2 ms |
9308 KB |
Output is correct |
10 |
Correct |
3 ms |
9308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
204 ms |
36812 KB |
Output is correct |
2 |
Correct |
571 ms |
68672 KB |
Output is correct |
3 |
Correct |
554 ms |
68356 KB |
Output is correct |
4 |
Correct |
63 ms |
26452 KB |
Output is correct |
5 |
Correct |
585 ms |
67656 KB |
Output is correct |
6 |
Correct |
579 ms |
69008 KB |
Output is correct |
7 |
Correct |
522 ms |
67708 KB |
Output is correct |
8 |
Correct |
543 ms |
67500 KB |
Output is correct |
9 |
Correct |
553 ms |
67564 KB |
Output is correct |
10 |
Correct |
546 ms |
68056 KB |
Output is correct |
11 |
Correct |
586 ms |
68084 KB |
Output is correct |
12 |
Correct |
536 ms |
67564 KB |
Output is correct |
13 |
Correct |
605 ms |
67848 KB |
Output is correct |
14 |
Correct |
530 ms |
67760 KB |
Output is correct |
15 |
Correct |
554 ms |
66796 KB |
Output is correct |
16 |
Correct |
586 ms |
68028 KB |
Output is correct |
17 |
Correct |
570 ms |
66848 KB |
Output is correct |
18 |
Correct |
585 ms |
68340 KB |
Output is correct |
19 |
Correct |
70 ms |
26456 KB |
Output is correct |
20 |
Correct |
534 ms |
68296 KB |
Output is correct |
21 |
Correct |
647 ms |
68748 KB |
Output is correct |
22 |
Correct |
100 ms |
33604 KB |
Output is correct |
23 |
Correct |
72 ms |
26964 KB |
Output is correct |
24 |
Correct |
90 ms |
33388 KB |
Output is correct |
25 |
Correct |
89 ms |
33844 KB |
Output is correct |
26 |
Correct |
85 ms |
27216 KB |
Output is correct |
27 |
Correct |
64 ms |
26464 KB |
Output is correct |
28 |
Correct |
89 ms |
33604 KB |
Output is correct |
29 |
Correct |
64 ms |
26452 KB |
Output is correct |
30 |
Correct |
105 ms |
34104 KB |
Output is correct |
31 |
Correct |
60 ms |
26456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9308 KB |
Output is correct |
2 |
Correct |
4 ms |
9544 KB |
Output is correct |
3 |
Correct |
4 ms |
9308 KB |
Output is correct |
4 |
Correct |
2 ms |
9308 KB |
Output is correct |
5 |
Correct |
4 ms |
9560 KB |
Output is correct |
6 |
Correct |
4 ms |
9308 KB |
Output is correct |
7 |
Correct |
2 ms |
9308 KB |
Output is correct |
8 |
Correct |
2 ms |
9308 KB |
Output is correct |
9 |
Correct |
4 ms |
9308 KB |
Output is correct |
10 |
Correct |
4 ms |
9308 KB |
Output is correct |
11 |
Correct |
4 ms |
9308 KB |
Output is correct |
12 |
Correct |
5 ms |
9312 KB |
Output is correct |
13 |
Correct |
4 ms |
9304 KB |
Output is correct |
14 |
Correct |
3 ms |
9308 KB |
Output is correct |
15 |
Correct |
4 ms |
9476 KB |
Output is correct |
16 |
Correct |
249 ms |
30584 KB |
Output is correct |
17 |
Correct |
761 ms |
68956 KB |
Output is correct |
18 |
Correct |
47 ms |
13896 KB |
Output is correct |
19 |
Correct |
230 ms |
35484 KB |
Output is correct |
20 |
Correct |
735 ms |
68860 KB |
Output is correct |
21 |
Correct |
372 ms |
39520 KB |
Output is correct |
22 |
Correct |
216 ms |
29132 KB |
Output is correct |
23 |
Correct |
682 ms |
69276 KB |
Output is correct |
24 |
Correct |
770 ms |
69044 KB |
Output is correct |
25 |
Correct |
749 ms |
68976 KB |
Output is correct |
26 |
Correct |
235 ms |
35236 KB |
Output is correct |
27 |
Correct |
263 ms |
35288 KB |
Output is correct |
28 |
Correct |
246 ms |
35504 KB |
Output is correct |
29 |
Correct |
235 ms |
35140 KB |
Output is correct |
30 |
Correct |
241 ms |
35804 KB |
Output is correct |
31 |
Correct |
2 ms |
9308 KB |
Output is correct |
32 |
Correct |
2 ms |
9276 KB |
Output is correct |
33 |
Correct |
2 ms |
9308 KB |
Output is correct |
34 |
Correct |
2 ms |
9308 KB |
Output is correct |
35 |
Correct |
2 ms |
9308 KB |
Output is correct |
36 |
Correct |
2 ms |
9308 KB |
Output is correct |
37 |
Correct |
2 ms |
9308 KB |
Output is correct |
38 |
Correct |
2 ms |
9304 KB |
Output is correct |
39 |
Correct |
2 ms |
9308 KB |
Output is correct |
40 |
Correct |
3 ms |
9308 KB |
Output is correct |
41 |
Correct |
204 ms |
36812 KB |
Output is correct |
42 |
Correct |
571 ms |
68672 KB |
Output is correct |
43 |
Correct |
554 ms |
68356 KB |
Output is correct |
44 |
Correct |
63 ms |
26452 KB |
Output is correct |
45 |
Correct |
585 ms |
67656 KB |
Output is correct |
46 |
Correct |
579 ms |
69008 KB |
Output is correct |
47 |
Correct |
522 ms |
67708 KB |
Output is correct |
48 |
Correct |
543 ms |
67500 KB |
Output is correct |
49 |
Correct |
553 ms |
67564 KB |
Output is correct |
50 |
Correct |
546 ms |
68056 KB |
Output is correct |
51 |
Correct |
586 ms |
68084 KB |
Output is correct |
52 |
Correct |
536 ms |
67564 KB |
Output is correct |
53 |
Correct |
605 ms |
67848 KB |
Output is correct |
54 |
Correct |
530 ms |
67760 KB |
Output is correct |
55 |
Correct |
554 ms |
66796 KB |
Output is correct |
56 |
Correct |
586 ms |
68028 KB |
Output is correct |
57 |
Correct |
570 ms |
66848 KB |
Output is correct |
58 |
Correct |
585 ms |
68340 KB |
Output is correct |
59 |
Correct |
70 ms |
26456 KB |
Output is correct |
60 |
Correct |
534 ms |
68296 KB |
Output is correct |
61 |
Correct |
647 ms |
68748 KB |
Output is correct |
62 |
Correct |
100 ms |
33604 KB |
Output is correct |
63 |
Correct |
72 ms |
26964 KB |
Output is correct |
64 |
Correct |
90 ms |
33388 KB |
Output is correct |
65 |
Correct |
89 ms |
33844 KB |
Output is correct |
66 |
Correct |
85 ms |
27216 KB |
Output is correct |
67 |
Correct |
64 ms |
26464 KB |
Output is correct |
68 |
Correct |
89 ms |
33604 KB |
Output is correct |
69 |
Correct |
64 ms |
26452 KB |
Output is correct |
70 |
Correct |
105 ms |
34104 KB |
Output is correct |
71 |
Correct |
60 ms |
26456 KB |
Output is correct |
72 |
Correct |
375 ms |
38480 KB |
Output is correct |
73 |
Correct |
682 ms |
68348 KB |
Output is correct |
74 |
Correct |
709 ms |
68456 KB |
Output is correct |
75 |
Correct |
735 ms |
70324 KB |
Output is correct |
76 |
Correct |
693 ms |
69416 KB |
Output is correct |
77 |
Correct |
720 ms |
68764 KB |
Output is correct |
78 |
Correct |
730 ms |
69156 KB |
Output is correct |
79 |
Correct |
721 ms |
69816 KB |
Output is correct |
80 |
Correct |
750 ms |
69468 KB |
Output is correct |
81 |
Correct |
734 ms |
70064 KB |
Output is correct |
82 |
Correct |
714 ms |
68268 KB |
Output is correct |
83 |
Correct |
775 ms |
69800 KB |
Output is correct |
84 |
Correct |
712 ms |
68648 KB |
Output is correct |
85 |
Correct |
750 ms |
69036 KB |
Output is correct |
86 |
Correct |
673 ms |
68820 KB |
Output is correct |
87 |
Correct |
721 ms |
69460 KB |
Output is correct |
88 |
Correct |
700 ms |
69248 KB |
Output is correct |
89 |
Correct |
252 ms |
29180 KB |
Output is correct |
90 |
Correct |
684 ms |
69116 KB |
Output is correct |
91 |
Correct |
736 ms |
70312 KB |
Output is correct |
92 |
Correct |
252 ms |
35492 KB |
Output is correct |
93 |
Correct |
227 ms |
29388 KB |
Output is correct |
94 |
Correct |
234 ms |
34872 KB |
Output is correct |
95 |
Correct |
274 ms |
35180 KB |
Output is correct |
96 |
Correct |
231 ms |
29136 KB |
Output is correct |
97 |
Correct |
236 ms |
29008 KB |
Output is correct |
98 |
Correct |
239 ms |
34904 KB |
Output is correct |
99 |
Correct |
282 ms |
28620 KB |
Output is correct |
100 |
Correct |
244 ms |
35228 KB |
Output is correct |