#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,zx,xc,i,j,za,z[1000009],tes,te,di[1000009],msh[1000009],dep[1000009],wv[1000009],pi,rmsh[1000009][18],mn[1000009][18],lf[1000009],rg[1000009],tim;
int bo[1000009];
vector <pair <int, int> > v[1000009];
pair <int, int> vv[1000009];
pair <int, pair <int, int> > qw[500009];
pair <int, int> f[1000009];
set <pair <int, int> > s;
set <pair <int, int> >::iterator t;
int fnd(int q){
if(msh[q]==0) return q; else return fnd(msh[q]);
}
void mrg(int q, int w, int r){
q=fnd(q);
w=fnd(w);
if(q==w) return;
if(dep[q]>dep[w]) swap(q,w);
pi++;
rmsh[wv[q]][0]=pi;
rmsh[wv[w]][0]=pi;
mn[wv[q]][0]=r;
mn[wv[w]][0]=r;
msh[q]=w;
vv[pi].first=wv[q];
vv[pi].second=wv[w];
wv[w]=pi;
dep[w]+=dep[q];
}
void dfs(int q){
bo[q]=i;
tim++;
rg[q]=lf[q]=tim;
if(vv[q].first==0) return;
dfs(vv[q].first);
dfs(vv[q].second);
if(rg[q]<rg[vv[q].first]) rg[q]=rg[vv[q].first];
if(rg[q]<rg[vv[q].second]) rg[q]=rg[vv[q].second];
}
bool anc(int q, int w){
if(lf[q]<=lf[w]&&rg[q]>=rg[w]) return 1; else return 0;
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>b;
for(i=1; i<=b; i++){
cin>>c>>d>>e;
qw[i].second.first=c;
qw[i].second.second=d;
v[c].push_back(make_pair(d,e));
v[d].push_back(make_pair(c,e));
}
cin>>za;
for(i=1; i<=a; i++) di[i]=1100000000;
for(i=1; i<=a; i++) for(j=0; j<=17; j++) mn[i][j]=1100000000;
for(i=1; i<=za; i++){
cin>>z[i];
di[z[i]]=0;
s.insert(make_pair(0,z[i]));
}
while(s.size()!=0){
d=(*s.begin()).first;
c=(*s.begin()).second;
s.erase(s.begin());
if(bo[c]==1) continue;
for(vector <pair <int, int> >::iterator it=v[c].begin(); it!=v[c].end(); it++){
if(di[(*it).first]>d+(*it).second){
di[(*it).first]=d+(*it).second;
s.insert(make_pair(di[(*it).first],(*it).first));
}
}
bo[c]=1;
}
for(i=1; i<=a; i++){
dep[i]=1;
wv[i]=i;
f[i].first=di[i];
f[i].second=i;
}
sort(f+1,f+a+1);
pi=a;
for(i=1; i<=b; i++) qw[i].first=min(di[qw[i].second.first],di[qw[i].second.second]);
sort(qw+1,qw+b+1);
for(i=b; i>=1; i--){
mrg(qw[i].second.first,qw[i].second.second,qw[i].first);
}
/*for(i=1; i<=a; i++){
c=f[i].second;
d=f[i].first;
for(vector <pair <int, long long> >::iterator it=v[c].begin(); it!=v[c].end(); it++){
mrg((*it).first,c,d);
}
}*/
for(i=pi; i>=1; i--){
bo[i]=0;
for(j=1; j<=17; j++){
rmsh[i][j]=rmsh[rmsh[i][j-1]][j-1];
mn[i][j]=min(mn[i][j-1],mn[rmsh[i][j-1]][j-1]);
}
}
for(i=pi; i>=1; i--){
if(bo[i]!=0) continue;
dfs(i);
}
cin>>tes;
for(te=1; te<=tes; te++){
cin>>c>>d;
zx=c;xc=d;
e=1100000000;
for(i=17; i>=0; i--){
if(rmsh[c][i]==0) continue;
if(anc(rmsh[c][i],d)==0){
if(e>mn[c][i]) e=mn[c][i];
c=rmsh[c][i];
}
}
if(e>mn[c][0]) e=mn[c][0];
c=rmsh[c][0];
c=d;
for(i=17; i>=0; i--){
if(rmsh[c][i]==0) continue;
if(anc(rmsh[c][i],d)==0){
if(e>mn[c][i]) e=mn[c][i];
c=rmsh[c][i];
}
}
if(e>mn[c][0]) e=mn[c][0];
c=rmsh[c][0];
cout<<e<<endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23932 KB |
Output is correct |
2 |
Correct |
28 ms |
24400 KB |
Output is correct |
3 |
Correct |
28 ms |
24312 KB |
Output is correct |
4 |
Correct |
27 ms |
23904 KB |
Output is correct |
5 |
Correct |
28 ms |
24312 KB |
Output is correct |
6 |
Correct |
28 ms |
24284 KB |
Output is correct |
7 |
Correct |
23 ms |
23928 KB |
Output is correct |
8 |
Correct |
23 ms |
23928 KB |
Output is correct |
9 |
Correct |
27 ms |
24312 KB |
Output is correct |
10 |
Correct |
28 ms |
24312 KB |
Output is correct |
11 |
Correct |
28 ms |
24312 KB |
Output is correct |
12 |
Correct |
28 ms |
24312 KB |
Output is correct |
13 |
Correct |
28 ms |
24248 KB |
Output is correct |
14 |
Correct |
27 ms |
24312 KB |
Output is correct |
15 |
Correct |
27 ms |
24312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23932 KB |
Output is correct |
2 |
Correct |
28 ms |
24400 KB |
Output is correct |
3 |
Correct |
28 ms |
24312 KB |
Output is correct |
4 |
Correct |
27 ms |
23904 KB |
Output is correct |
5 |
Correct |
28 ms |
24312 KB |
Output is correct |
6 |
Correct |
28 ms |
24284 KB |
Output is correct |
7 |
Correct |
23 ms |
23928 KB |
Output is correct |
8 |
Correct |
23 ms |
23928 KB |
Output is correct |
9 |
Correct |
27 ms |
24312 KB |
Output is correct |
10 |
Correct |
28 ms |
24312 KB |
Output is correct |
11 |
Correct |
28 ms |
24312 KB |
Output is correct |
12 |
Correct |
28 ms |
24312 KB |
Output is correct |
13 |
Correct |
28 ms |
24248 KB |
Output is correct |
14 |
Correct |
27 ms |
24312 KB |
Output is correct |
15 |
Correct |
27 ms |
24312 KB |
Output is correct |
16 |
Correct |
607 ms |
56932 KB |
Output is correct |
17 |
Correct |
1196 ms |
84044 KB |
Output is correct |
18 |
Correct |
102 ms |
30328 KB |
Output is correct |
19 |
Correct |
562 ms |
69496 KB |
Output is correct |
20 |
Correct |
1165 ms |
84012 KB |
Output is correct |
21 |
Correct |
775 ms |
71072 KB |
Output is correct |
22 |
Correct |
571 ms |
64528 KB |
Output is correct |
23 |
Correct |
1100 ms |
84076 KB |
Output is correct |
24 |
Correct |
1126 ms |
84024 KB |
Output is correct |
25 |
Correct |
1166 ms |
84256 KB |
Output is correct |
26 |
Correct |
563 ms |
69164 KB |
Output is correct |
27 |
Correct |
568 ms |
69348 KB |
Output is correct |
28 |
Correct |
574 ms |
69100 KB |
Output is correct |
29 |
Correct |
571 ms |
69316 KB |
Output is correct |
30 |
Correct |
573 ms |
69388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23928 KB |
Output is correct |
2 |
Correct |
23 ms |
23928 KB |
Output is correct |
3 |
Correct |
23 ms |
23928 KB |
Output is correct |
4 |
Correct |
24 ms |
23928 KB |
Output is correct |
5 |
Correct |
24 ms |
23928 KB |
Output is correct |
6 |
Correct |
24 ms |
23928 KB |
Output is correct |
7 |
Correct |
23 ms |
23904 KB |
Output is correct |
8 |
Correct |
23 ms |
23928 KB |
Output is correct |
9 |
Correct |
23 ms |
23928 KB |
Output is correct |
10 |
Correct |
23 ms |
23928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
402 ms |
69948 KB |
Output is correct |
2 |
Correct |
731 ms |
83604 KB |
Output is correct |
3 |
Correct |
737 ms |
83652 KB |
Output is correct |
4 |
Correct |
343 ms |
62780 KB |
Output is correct |
5 |
Correct |
746 ms |
83620 KB |
Output is correct |
6 |
Correct |
741 ms |
83508 KB |
Output is correct |
7 |
Correct |
714 ms |
83540 KB |
Output is correct |
8 |
Correct |
739 ms |
83632 KB |
Output is correct |
9 |
Correct |
726 ms |
83600 KB |
Output is correct |
10 |
Correct |
748 ms |
83696 KB |
Output is correct |
11 |
Correct |
765 ms |
83684 KB |
Output is correct |
12 |
Correct |
751 ms |
83652 KB |
Output is correct |
13 |
Correct |
752 ms |
83536 KB |
Output is correct |
14 |
Correct |
750 ms |
83736 KB |
Output is correct |
15 |
Correct |
756 ms |
83904 KB |
Output is correct |
16 |
Correct |
745 ms |
83644 KB |
Output is correct |
17 |
Correct |
750 ms |
83624 KB |
Output is correct |
18 |
Correct |
733 ms |
83608 KB |
Output is correct |
19 |
Correct |
222 ms |
63428 KB |
Output is correct |
20 |
Correct |
746 ms |
83732 KB |
Output is correct |
21 |
Correct |
658 ms |
81960 KB |
Output is correct |
22 |
Correct |
208 ms |
68976 KB |
Output is correct |
23 |
Correct |
242 ms |
62832 KB |
Output is correct |
24 |
Correct |
208 ms |
68928 KB |
Output is correct |
25 |
Correct |
204 ms |
68968 KB |
Output is correct |
26 |
Correct |
260 ms |
62844 KB |
Output is correct |
27 |
Correct |
232 ms |
62680 KB |
Output is correct |
28 |
Correct |
208 ms |
68892 KB |
Output is correct |
29 |
Correct |
235 ms |
62712 KB |
Output is correct |
30 |
Correct |
203 ms |
69068 KB |
Output is correct |
31 |
Correct |
239 ms |
62712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23932 KB |
Output is correct |
2 |
Correct |
28 ms |
24400 KB |
Output is correct |
3 |
Correct |
28 ms |
24312 KB |
Output is correct |
4 |
Correct |
27 ms |
23904 KB |
Output is correct |
5 |
Correct |
28 ms |
24312 KB |
Output is correct |
6 |
Correct |
28 ms |
24284 KB |
Output is correct |
7 |
Correct |
23 ms |
23928 KB |
Output is correct |
8 |
Correct |
23 ms |
23928 KB |
Output is correct |
9 |
Correct |
27 ms |
24312 KB |
Output is correct |
10 |
Correct |
28 ms |
24312 KB |
Output is correct |
11 |
Correct |
28 ms |
24312 KB |
Output is correct |
12 |
Correct |
28 ms |
24312 KB |
Output is correct |
13 |
Correct |
28 ms |
24248 KB |
Output is correct |
14 |
Correct |
27 ms |
24312 KB |
Output is correct |
15 |
Correct |
27 ms |
24312 KB |
Output is correct |
16 |
Correct |
607 ms |
56932 KB |
Output is correct |
17 |
Correct |
1196 ms |
84044 KB |
Output is correct |
18 |
Correct |
102 ms |
30328 KB |
Output is correct |
19 |
Correct |
562 ms |
69496 KB |
Output is correct |
20 |
Correct |
1165 ms |
84012 KB |
Output is correct |
21 |
Correct |
775 ms |
71072 KB |
Output is correct |
22 |
Correct |
571 ms |
64528 KB |
Output is correct |
23 |
Correct |
1100 ms |
84076 KB |
Output is correct |
24 |
Correct |
1126 ms |
84024 KB |
Output is correct |
25 |
Correct |
1166 ms |
84256 KB |
Output is correct |
26 |
Correct |
563 ms |
69164 KB |
Output is correct |
27 |
Correct |
568 ms |
69348 KB |
Output is correct |
28 |
Correct |
574 ms |
69100 KB |
Output is correct |
29 |
Correct |
571 ms |
69316 KB |
Output is correct |
30 |
Correct |
573 ms |
69388 KB |
Output is correct |
31 |
Correct |
24 ms |
23928 KB |
Output is correct |
32 |
Correct |
23 ms |
23928 KB |
Output is correct |
33 |
Correct |
23 ms |
23928 KB |
Output is correct |
34 |
Correct |
24 ms |
23928 KB |
Output is correct |
35 |
Correct |
24 ms |
23928 KB |
Output is correct |
36 |
Correct |
24 ms |
23928 KB |
Output is correct |
37 |
Correct |
23 ms |
23904 KB |
Output is correct |
38 |
Correct |
23 ms |
23928 KB |
Output is correct |
39 |
Correct |
23 ms |
23928 KB |
Output is correct |
40 |
Correct |
23 ms |
23928 KB |
Output is correct |
41 |
Correct |
402 ms |
69948 KB |
Output is correct |
42 |
Correct |
731 ms |
83604 KB |
Output is correct |
43 |
Correct |
737 ms |
83652 KB |
Output is correct |
44 |
Correct |
343 ms |
62780 KB |
Output is correct |
45 |
Correct |
746 ms |
83620 KB |
Output is correct |
46 |
Correct |
741 ms |
83508 KB |
Output is correct |
47 |
Correct |
714 ms |
83540 KB |
Output is correct |
48 |
Correct |
739 ms |
83632 KB |
Output is correct |
49 |
Correct |
726 ms |
83600 KB |
Output is correct |
50 |
Correct |
748 ms |
83696 KB |
Output is correct |
51 |
Correct |
765 ms |
83684 KB |
Output is correct |
52 |
Correct |
751 ms |
83652 KB |
Output is correct |
53 |
Correct |
752 ms |
83536 KB |
Output is correct |
54 |
Correct |
750 ms |
83736 KB |
Output is correct |
55 |
Correct |
756 ms |
83904 KB |
Output is correct |
56 |
Correct |
745 ms |
83644 KB |
Output is correct |
57 |
Correct |
750 ms |
83624 KB |
Output is correct |
58 |
Correct |
733 ms |
83608 KB |
Output is correct |
59 |
Correct |
222 ms |
63428 KB |
Output is correct |
60 |
Correct |
746 ms |
83732 KB |
Output is correct |
61 |
Correct |
658 ms |
81960 KB |
Output is correct |
62 |
Correct |
208 ms |
68976 KB |
Output is correct |
63 |
Correct |
242 ms |
62832 KB |
Output is correct |
64 |
Correct |
208 ms |
68928 KB |
Output is correct |
65 |
Correct |
204 ms |
68968 KB |
Output is correct |
66 |
Correct |
260 ms |
62844 KB |
Output is correct |
67 |
Correct |
232 ms |
62680 KB |
Output is correct |
68 |
Correct |
208 ms |
68892 KB |
Output is correct |
69 |
Correct |
235 ms |
62712 KB |
Output is correct |
70 |
Correct |
203 ms |
69068 KB |
Output is correct |
71 |
Correct |
239 ms |
62712 KB |
Output is correct |
72 |
Correct |
803 ms |
70564 KB |
Output is correct |
73 |
Correct |
1200 ms |
84188 KB |
Output is correct |
74 |
Correct |
1184 ms |
84052 KB |
Output is correct |
75 |
Correct |
1104 ms |
84060 KB |
Output is correct |
76 |
Correct |
1174 ms |
84136 KB |
Output is correct |
77 |
Correct |
1138 ms |
84060 KB |
Output is correct |
78 |
Correct |
1148 ms |
84020 KB |
Output is correct |
79 |
Correct |
1205 ms |
84116 KB |
Output is correct |
80 |
Correct |
1169 ms |
84060 KB |
Output is correct |
81 |
Correct |
1176 ms |
84008 KB |
Output is correct |
82 |
Correct |
1176 ms |
84076 KB |
Output is correct |
83 |
Correct |
1110 ms |
84004 KB |
Output is correct |
84 |
Correct |
1165 ms |
84244 KB |
Output is correct |
85 |
Correct |
1168 ms |
84252 KB |
Output is correct |
86 |
Correct |
1156 ms |
84048 KB |
Output is correct |
87 |
Correct |
1227 ms |
83964 KB |
Output is correct |
88 |
Correct |
1179 ms |
84148 KB |
Output is correct |
89 |
Correct |
640 ms |
64436 KB |
Output is correct |
90 |
Correct |
1176 ms |
84040 KB |
Output is correct |
91 |
Correct |
1084 ms |
82284 KB |
Output is correct |
92 |
Correct |
598 ms |
69336 KB |
Output is correct |
93 |
Correct |
620 ms |
63484 KB |
Output is correct |
94 |
Correct |
596 ms |
69068 KB |
Output is correct |
95 |
Correct |
600 ms |
69304 KB |
Output is correct |
96 |
Correct |
617 ms |
63224 KB |
Output is correct |
97 |
Correct |
661 ms |
63320 KB |
Output is correct |
98 |
Correct |
610 ms |
69144 KB |
Output is correct |
99 |
Correct |
645 ms |
63268 KB |
Output is correct |
100 |
Correct |
596 ms |
69356 KB |
Output is correct |