#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int n,m,N,q,lg=17,timer=1,ans[100005];
map<pair<int,int>,int> mp;
vector<int> g[100005],d,used,p,Size,g1[100005],dp[100005],tin,tout;
multiset<pair<int,int> > s;
vector<pii> ed;
void MS(){
for(int k=1;k<=n;k++){
p[k]=k;
Size[k]=d[k];
}
}
int FS(int v){
if(p[v]==v) return v;
return p[v]=FS(p[v]);
}
void US(int a,int b){
a=FS(a);
b=FS(b);
if(a!=b){
g1[a].push_back(b);
g1[b].push_back(a);
p[b]=a;
Size[a]=min(Size[a],Size[b]);
}
}
void DFS(int v,int p){
used[v]=1;
dp[v][0]=p;
for(int k=1;k<=lg;k++)
dp[v][k]=dp[dp[v][k-1]][k-1];
tin[v]=timer++;
for(int k=0;k<g1[v].size();k++){
int to=g1[v][k];
if(used[to]==0)
DFS(to,v);
}
tout[v]=timer++;
}
bool tree(int a,int b){
if(tin[a]<=tin[b] && tout[a]>=tout[b])
return true;
return false;
}
int LCA(int a,int b){
if(tree(a,b)) return a;
if(tree(b,a)) return b;
int t=a;
for(int k=17;k>=0;k--){
if(dp[t][k]!=0){
int to=dp[t][k];
if(!tree(to,b))
t=to;
}
}
return dp[t][0];
}
main(){
cin>>n>>m;
for(int k=1;k<=m;k++){
int a,b,c;
cin>>a>>b>>c;
mp[{a,b}]=c;
mp[{b,a}]=c;
g[a].push_back(b);
g[b].push_back(a);
}
cin>>N;
d.resize(n+1,INT_MAX);
used.resize(n+1,0);
for(int k=1;k<=N;k++){
int qal;
cin>>qal;
d[qal]=0;
s.insert({0,qal});
}
while(!s.empty()){
int v=s.begin()->second;
used[v]=1;
s.erase(s.begin());
for(int k=0;k<g[v].size();k++){
int to=g[v][k];
if(used[to]==0 && d[to]>d[v]+mp[{v,to}]){
d[to]=d[v]+mp[{to,v}];
s.insert({d[to],to});
}
}
}
for(int k=1;k<=n;k++){
ed.push_back({d[k],k});
}
sort(ed.begin(),ed.end());
reverse(ed.begin(),ed.end());
cin>>q;
Size.resize(n+1,0);
p.resize(n+1,0);
used.resize(0);
used.resize(n+1,0);
MS();
for(int k=0;k<ed.size();k++){
int v=ed[k].y;
used[v]=1;
for(int k=0;k<g[v].size();k++)
if(used[g[v][k]])
US(v,g[v][k]);
}
used.resize(0);
used.resize(n+1,0);
tin.resize(n+1,0);
tout.resize(n+1,0);
for(int k=0;k<=n;k++)
dp[k].resize(18,0);
DFS(ed[ed.size()-1].y,ed[ed.size()-1].y);
for(int k=0;k<q;k++){
int a,b;
cin>>a>>b;
int lc=LCA(a,b);
cout<<d[lc]<<endl;
}
return 0;
}
Compilation message
plan.cpp: In function 'void DFS(int, int)':
plan.cpp:34:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int k=1;k<=lg;k++)
^~~
plan.cpp:36:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
tin[v]=timer++;
^~~
plan.cpp:37:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<g1[v].size();k++){
~^~~~~~~~~~~~~
plan.cpp: At global scope:
plan.cpp:62:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
plan.cpp: In function 'int main()':
plan.cpp:85:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<g[v].size();k++){
~^~~~~~~~~~~~
plan.cpp:104:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<ed.size();k++){
~^~~~~~~~~~
plan.cpp:107:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<g[v].size();k++)
~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7288 KB |
Output is correct |
2 |
Correct |
14 ms |
7644 KB |
Output is correct |
3 |
Correct |
14 ms |
7672 KB |
Output is correct |
4 |
Correct |
8 ms |
7288 KB |
Output is correct |
5 |
Correct |
15 ms |
7676 KB |
Output is correct |
6 |
Correct |
15 ms |
7672 KB |
Output is correct |
7 |
Correct |
9 ms |
7544 KB |
Output is correct |
8 |
Correct |
8 ms |
7416 KB |
Output is correct |
9 |
Correct |
15 ms |
7672 KB |
Output is correct |
10 |
Correct |
14 ms |
7672 KB |
Output is correct |
11 |
Correct |
15 ms |
7672 KB |
Output is correct |
12 |
Correct |
14 ms |
7672 KB |
Output is correct |
13 |
Correct |
14 ms |
7672 KB |
Output is correct |
14 |
Correct |
14 ms |
7744 KB |
Output is correct |
15 |
Correct |
14 ms |
7672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7288 KB |
Output is correct |
2 |
Correct |
14 ms |
7644 KB |
Output is correct |
3 |
Correct |
14 ms |
7672 KB |
Output is correct |
4 |
Correct |
8 ms |
7288 KB |
Output is correct |
5 |
Correct |
15 ms |
7676 KB |
Output is correct |
6 |
Correct |
15 ms |
7672 KB |
Output is correct |
7 |
Correct |
9 ms |
7544 KB |
Output is correct |
8 |
Correct |
8 ms |
7416 KB |
Output is correct |
9 |
Correct |
15 ms |
7672 KB |
Output is correct |
10 |
Correct |
14 ms |
7672 KB |
Output is correct |
11 |
Correct |
15 ms |
7672 KB |
Output is correct |
12 |
Correct |
14 ms |
7672 KB |
Output is correct |
13 |
Correct |
14 ms |
7672 KB |
Output is correct |
14 |
Correct |
14 ms |
7744 KB |
Output is correct |
15 |
Correct |
14 ms |
7672 KB |
Output is correct |
16 |
Correct |
924 ms |
35272 KB |
Output is correct |
17 |
Correct |
3628 ms |
96548 KB |
Output is correct |
18 |
Correct |
190 ms |
15328 KB |
Output is correct |
19 |
Correct |
1056 ms |
38468 KB |
Output is correct |
20 |
Correct |
3488 ms |
96388 KB |
Output is correct |
21 |
Correct |
1547 ms |
53316 KB |
Output is correct |
22 |
Correct |
951 ms |
42728 KB |
Output is correct |
23 |
Correct |
3619 ms |
96328 KB |
Output is correct |
24 |
Correct |
3593 ms |
96340 KB |
Output is correct |
25 |
Correct |
3616 ms |
96172 KB |
Output is correct |
26 |
Correct |
1149 ms |
38200 KB |
Output is correct |
27 |
Correct |
1022 ms |
38228 KB |
Output is correct |
28 |
Correct |
1336 ms |
38184 KB |
Output is correct |
29 |
Correct |
1069 ms |
38328 KB |
Output is correct |
30 |
Correct |
930 ms |
38412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
8 ms |
7416 KB |
Output is correct |
3 |
Correct |
8 ms |
7288 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
9 ms |
7332 KB |
Output is correct |
6 |
Correct |
8 ms |
7416 KB |
Output is correct |
7 |
Correct |
8 ms |
7416 KB |
Output is correct |
8 |
Correct |
8 ms |
7288 KB |
Output is correct |
9 |
Correct |
9 ms |
7416 KB |
Output is correct |
10 |
Correct |
8 ms |
7416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1266 ms |
53148 KB |
Output is correct |
2 |
Correct |
3188 ms |
96104 KB |
Output is correct |
3 |
Correct |
3219 ms |
95892 KB |
Output is correct |
4 |
Correct |
532 ms |
39548 KB |
Output is correct |
5 |
Correct |
3213 ms |
96020 KB |
Output is correct |
6 |
Correct |
3240 ms |
95892 KB |
Output is correct |
7 |
Correct |
3283 ms |
95944 KB |
Output is correct |
8 |
Correct |
3286 ms |
95868 KB |
Output is correct |
9 |
Correct |
3223 ms |
95916 KB |
Output is correct |
10 |
Correct |
3259 ms |
96232 KB |
Output is correct |
11 |
Correct |
3266 ms |
96820 KB |
Output is correct |
12 |
Correct |
3234 ms |
97752 KB |
Output is correct |
13 |
Correct |
3242 ms |
97440 KB |
Output is correct |
14 |
Correct |
3283 ms |
97468 KB |
Output is correct |
15 |
Correct |
3171 ms |
97792 KB |
Output is correct |
16 |
Correct |
3237 ms |
97856 KB |
Output is correct |
17 |
Correct |
3283 ms |
97816 KB |
Output is correct |
18 |
Correct |
3460 ms |
97400 KB |
Output is correct |
19 |
Correct |
548 ms |
42792 KB |
Output is correct |
20 |
Correct |
3205 ms |
97436 KB |
Output is correct |
21 |
Correct |
2842 ms |
97332 KB |
Output is correct |
22 |
Correct |
594 ms |
38940 KB |
Output is correct |
23 |
Correct |
567 ms |
39304 KB |
Output is correct |
24 |
Correct |
750 ms |
38992 KB |
Output is correct |
25 |
Correct |
627 ms |
38900 KB |
Output is correct |
26 |
Correct |
617 ms |
38608 KB |
Output is correct |
27 |
Correct |
529 ms |
40524 KB |
Output is correct |
28 |
Correct |
876 ms |
39108 KB |
Output is correct |
29 |
Correct |
536 ms |
40540 KB |
Output is correct |
30 |
Correct |
671 ms |
38948 KB |
Output is correct |
31 |
Correct |
551 ms |
40552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7288 KB |
Output is correct |
2 |
Correct |
14 ms |
7644 KB |
Output is correct |
3 |
Correct |
14 ms |
7672 KB |
Output is correct |
4 |
Correct |
8 ms |
7288 KB |
Output is correct |
5 |
Correct |
15 ms |
7676 KB |
Output is correct |
6 |
Correct |
15 ms |
7672 KB |
Output is correct |
7 |
Correct |
9 ms |
7544 KB |
Output is correct |
8 |
Correct |
8 ms |
7416 KB |
Output is correct |
9 |
Correct |
15 ms |
7672 KB |
Output is correct |
10 |
Correct |
14 ms |
7672 KB |
Output is correct |
11 |
Correct |
15 ms |
7672 KB |
Output is correct |
12 |
Correct |
14 ms |
7672 KB |
Output is correct |
13 |
Correct |
14 ms |
7672 KB |
Output is correct |
14 |
Correct |
14 ms |
7744 KB |
Output is correct |
15 |
Correct |
14 ms |
7672 KB |
Output is correct |
16 |
Correct |
924 ms |
35272 KB |
Output is correct |
17 |
Correct |
3628 ms |
96548 KB |
Output is correct |
18 |
Correct |
190 ms |
15328 KB |
Output is correct |
19 |
Correct |
1056 ms |
38468 KB |
Output is correct |
20 |
Correct |
3488 ms |
96388 KB |
Output is correct |
21 |
Correct |
1547 ms |
53316 KB |
Output is correct |
22 |
Correct |
951 ms |
42728 KB |
Output is correct |
23 |
Correct |
3619 ms |
96328 KB |
Output is correct |
24 |
Correct |
3593 ms |
96340 KB |
Output is correct |
25 |
Correct |
3616 ms |
96172 KB |
Output is correct |
26 |
Correct |
1149 ms |
38200 KB |
Output is correct |
27 |
Correct |
1022 ms |
38228 KB |
Output is correct |
28 |
Correct |
1336 ms |
38184 KB |
Output is correct |
29 |
Correct |
1069 ms |
38328 KB |
Output is correct |
30 |
Correct |
930 ms |
38412 KB |
Output is correct |
31 |
Correct |
8 ms |
7416 KB |
Output is correct |
32 |
Correct |
8 ms |
7416 KB |
Output is correct |
33 |
Correct |
8 ms |
7288 KB |
Output is correct |
34 |
Correct |
8 ms |
7416 KB |
Output is correct |
35 |
Correct |
9 ms |
7332 KB |
Output is correct |
36 |
Correct |
8 ms |
7416 KB |
Output is correct |
37 |
Correct |
8 ms |
7416 KB |
Output is correct |
38 |
Correct |
8 ms |
7288 KB |
Output is correct |
39 |
Correct |
9 ms |
7416 KB |
Output is correct |
40 |
Correct |
8 ms |
7416 KB |
Output is correct |
41 |
Correct |
1266 ms |
53148 KB |
Output is correct |
42 |
Correct |
3188 ms |
96104 KB |
Output is correct |
43 |
Correct |
3219 ms |
95892 KB |
Output is correct |
44 |
Correct |
532 ms |
39548 KB |
Output is correct |
45 |
Correct |
3213 ms |
96020 KB |
Output is correct |
46 |
Correct |
3240 ms |
95892 KB |
Output is correct |
47 |
Correct |
3283 ms |
95944 KB |
Output is correct |
48 |
Correct |
3286 ms |
95868 KB |
Output is correct |
49 |
Correct |
3223 ms |
95916 KB |
Output is correct |
50 |
Correct |
3259 ms |
96232 KB |
Output is correct |
51 |
Correct |
3266 ms |
96820 KB |
Output is correct |
52 |
Correct |
3234 ms |
97752 KB |
Output is correct |
53 |
Correct |
3242 ms |
97440 KB |
Output is correct |
54 |
Correct |
3283 ms |
97468 KB |
Output is correct |
55 |
Correct |
3171 ms |
97792 KB |
Output is correct |
56 |
Correct |
3237 ms |
97856 KB |
Output is correct |
57 |
Correct |
3283 ms |
97816 KB |
Output is correct |
58 |
Correct |
3460 ms |
97400 KB |
Output is correct |
59 |
Correct |
548 ms |
42792 KB |
Output is correct |
60 |
Correct |
3205 ms |
97436 KB |
Output is correct |
61 |
Correct |
2842 ms |
97332 KB |
Output is correct |
62 |
Correct |
594 ms |
38940 KB |
Output is correct |
63 |
Correct |
567 ms |
39304 KB |
Output is correct |
64 |
Correct |
750 ms |
38992 KB |
Output is correct |
65 |
Correct |
627 ms |
38900 KB |
Output is correct |
66 |
Correct |
617 ms |
38608 KB |
Output is correct |
67 |
Correct |
529 ms |
40524 KB |
Output is correct |
68 |
Correct |
876 ms |
39108 KB |
Output is correct |
69 |
Correct |
536 ms |
40540 KB |
Output is correct |
70 |
Correct |
671 ms |
38948 KB |
Output is correct |
71 |
Correct |
551 ms |
40552 KB |
Output is correct |
72 |
Correct |
1685 ms |
54688 KB |
Output is correct |
73 |
Correct |
3657 ms |
97448 KB |
Output is correct |
74 |
Correct |
3644 ms |
97476 KB |
Output is correct |
75 |
Correct |
3806 ms |
98044 KB |
Output is correct |
76 |
Correct |
3653 ms |
98100 KB |
Output is correct |
77 |
Correct |
3654 ms |
97784 KB |
Output is correct |
78 |
Correct |
3629 ms |
98972 KB |
Output is correct |
79 |
Correct |
3628 ms |
98724 KB |
Output is correct |
80 |
Correct |
3618 ms |
99896 KB |
Output is correct |
81 |
Correct |
3616 ms |
99592 KB |
Output is correct |
82 |
Correct |
3636 ms |
101228 KB |
Output is correct |
83 |
Correct |
3710 ms |
102308 KB |
Output is correct |
84 |
Correct |
3631 ms |
102904 KB |
Output is correct |
85 |
Correct |
3729 ms |
101768 KB |
Output is correct |
86 |
Correct |
3718 ms |
103040 KB |
Output is correct |
87 |
Correct |
3684 ms |
103604 KB |
Output is correct |
88 |
Correct |
3632 ms |
104008 KB |
Output is correct |
89 |
Correct |
959 ms |
45548 KB |
Output is correct |
90 |
Correct |
3660 ms |
103052 KB |
Output is correct |
91 |
Correct |
3238 ms |
104396 KB |
Output is correct |
92 |
Correct |
985 ms |
41052 KB |
Output is correct |
93 |
Correct |
1008 ms |
41880 KB |
Output is correct |
94 |
Correct |
1366 ms |
41272 KB |
Output is correct |
95 |
Correct |
1012 ms |
41232 KB |
Output is correct |
96 |
Correct |
1053 ms |
40648 KB |
Output is correct |
97 |
Correct |
1010 ms |
42960 KB |
Output is correct |
98 |
Correct |
1223 ms |
41000 KB |
Output is correct |
99 |
Correct |
996 ms |
42868 KB |
Output is correct |
100 |
Correct |
1135 ms |
41044 KB |
Output is correct |