#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=2e5+5;
const ll MOD=1e9+7;
const ll INF=(1LL<<60);
const ld pi=acos(-1);
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lwb lower_bound
#define ALL(_a) _a.begin(),_a.end()
#define SZ(_a) (ll)_a.size()
struct DSU{
ll dir[N],sz[N];
void init(ll n){
REP1(i,n)dir[i]=i,sz[i]=1;
}
ll find(ll id){
return (dir[id]==id?id:dir[id]=find(dir[id]));
}
bool is(ll x,ll y){
return (find(x)==find(y));
}
void uni(ll x,ll y){
x=find(x);y=find(y);
if(x==y)return ;
if(sz[x]>sz[y])swap(x,y);
sz[y]+=sz[x];
dir[x]=y;
}
}dsu;
ll depth[N],weight[N][20],anc[N][20];
vector<pll> v[N];
void DFS(ll nd,ll pa,ll c){
depth[nd]=depth[pa]+1;
anc[nd][0]=pa;weight[nd][0]=c;
REP1(i,17){
anc[nd][i]=anc[anc[nd][i-1]][i-1];
weight[nd][i]=min(weight[nd][i-1],weight[anc[nd][i-1]][i-1]);
}
for(auto i:v[nd]){
if(i.X==pa)continue;
DFS(i.X,nd,i.Y);
}
}
ll lca(ll nda,ll ndb){
ll ret=INF;
if(depth[nda]<depth[ndb])swap(nda,ndb);
for(int i=17;i>=0;i--){
if(depth[anc[nda][i]]>=depth[ndb]){
ret=min(ret,weight[nda][i]);
nda=anc[nda][i];
}
}
if(nda==ndb)return ret;
for(int i=17;i>=0;i--){
if(anc[nda][i]!=anc[ndb][i]){
ret=min(ret,min(weight[nda][i],weight[ndb][i]));
nda=anc[nda][i];ndb=anc[ndb][i];
}
}
return min(ret,min(weight[nda][0],weight[ndb][0]));
}
ll n,m,x,y,c;
vector<pll> ed;
ll dis[N];
priority_queue<pll,vector<pll>,greater<pll> > pq;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
dsu.init(n);
REP(i,m){
cin>>x>>y>>c;
v[x].pb(mp(y,c));
v[y].pb(mp(x,c));
ed.pb(mp(x,y));
}
REP1(i,n)dis[i]=INF;
cin>>m;
REP(i,m){
cin>>x;
pq.push(mp(dis[x]=0,x));
}
while(SZ(pq)){
x=pq.top().Y,y=pq.top().X;pq.pop();
if(y>dis[x])continue;
for(auto i:v[x]){
if(dis[i.X]>y+i.Y){
pq.push(mp(dis[i.X]=i.Y+y,i.X));
}
}
}
//
REP1(i,n)v[i].clear();
sort(ed.begin(),ed.end(),[&](pll A,pll B){
return min(dis[A.X],dis[A.Y])>min(dis[B.X],dis[B.Y]);
});
//cout<<"EDGE\n";
for(auto i:ed){
if(dsu.is(i.X,i.Y))continue;
dsu.uni(i.X,i.Y);
//cout<<i.X<<" "<<i.Y<<" "<<min(dis[i.X],dis[i.Y])<<"\n";
v[i.X].pb(mp(i.Y,min(dis[i.X],dis[i.Y])));
v[i.Y].pb(mp(i.X,min(dis[i.X],dis[i.Y])));
}
DFS(1,0,INF);
cin>>m;
while(m--){
cin>>x>>y;
cout<<lca(x,y)<<"\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5484 KB |
Output is correct |
3 |
Correct |
6 ms |
5484 KB |
Output is correct |
4 |
Correct |
3 ms |
5100 KB |
Output is correct |
5 |
Correct |
5 ms |
5612 KB |
Output is correct |
6 |
Correct |
4 ms |
5484 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
4 ms |
5100 KB |
Output is correct |
9 |
Correct |
5 ms |
5484 KB |
Output is correct |
10 |
Correct |
5 ms |
5484 KB |
Output is correct |
11 |
Correct |
5 ms |
5504 KB |
Output is correct |
12 |
Correct |
6 ms |
5484 KB |
Output is correct |
13 |
Correct |
5 ms |
5484 KB |
Output is correct |
14 |
Correct |
5 ms |
5484 KB |
Output is correct |
15 |
Correct |
5 ms |
5484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5484 KB |
Output is correct |
3 |
Correct |
6 ms |
5484 KB |
Output is correct |
4 |
Correct |
3 ms |
5100 KB |
Output is correct |
5 |
Correct |
5 ms |
5612 KB |
Output is correct |
6 |
Correct |
4 ms |
5484 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
4 ms |
5100 KB |
Output is correct |
9 |
Correct |
5 ms |
5484 KB |
Output is correct |
10 |
Correct |
5 ms |
5484 KB |
Output is correct |
11 |
Correct |
5 ms |
5504 KB |
Output is correct |
12 |
Correct |
6 ms |
5484 KB |
Output is correct |
13 |
Correct |
5 ms |
5484 KB |
Output is correct |
14 |
Correct |
5 ms |
5484 KB |
Output is correct |
15 |
Correct |
5 ms |
5484 KB |
Output is correct |
16 |
Correct |
239 ms |
40976 KB |
Output is correct |
17 |
Correct |
666 ms |
78792 KB |
Output is correct |
18 |
Correct |
40 ms |
13172 KB |
Output is correct |
19 |
Correct |
193 ms |
48716 KB |
Output is correct |
20 |
Correct |
639 ms |
78768 KB |
Output is correct |
21 |
Correct |
346 ms |
57940 KB |
Output is correct |
22 |
Correct |
244 ms |
52080 KB |
Output is correct |
23 |
Correct |
621 ms |
78756 KB |
Output is correct |
24 |
Correct |
618 ms |
78768 KB |
Output is correct |
25 |
Correct |
641 ms |
78748 KB |
Output is correct |
26 |
Correct |
200 ms |
48340 KB |
Output is correct |
27 |
Correct |
200 ms |
48460 KB |
Output is correct |
28 |
Correct |
195 ms |
48332 KB |
Output is correct |
29 |
Correct |
229 ms |
48588 KB |
Output is correct |
30 |
Correct |
210 ms |
48616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
3 ms |
5100 KB |
Output is correct |
5 |
Correct |
4 ms |
5100 KB |
Output is correct |
6 |
Correct |
4 ms |
5100 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
4 ms |
5100 KB |
Output is correct |
9 |
Correct |
4 ms |
5100 KB |
Output is correct |
10 |
Correct |
4 ms |
5100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
294 ms |
56276 KB |
Output is correct |
2 |
Correct |
561 ms |
78524 KB |
Output is correct |
3 |
Correct |
533 ms |
78748 KB |
Output is correct |
4 |
Correct |
167 ms |
49084 KB |
Output is correct |
5 |
Correct |
553 ms |
78536 KB |
Output is correct |
6 |
Correct |
616 ms |
78600 KB |
Output is correct |
7 |
Correct |
532 ms |
78792 KB |
Output is correct |
8 |
Correct |
564 ms |
78764 KB |
Output is correct |
9 |
Correct |
551 ms |
78576 KB |
Output is correct |
10 |
Correct |
546 ms |
78596 KB |
Output is correct |
11 |
Correct |
564 ms |
78668 KB |
Output is correct |
12 |
Correct |
558 ms |
78536 KB |
Output is correct |
13 |
Correct |
550 ms |
78536 KB |
Output is correct |
14 |
Correct |
540 ms |
78536 KB |
Output is correct |
15 |
Correct |
550 ms |
80840 KB |
Output is correct |
16 |
Correct |
536 ms |
78672 KB |
Output is correct |
17 |
Correct |
586 ms |
78568 KB |
Output is correct |
18 |
Correct |
531 ms |
78536 KB |
Output is correct |
19 |
Correct |
158 ms |
50652 KB |
Output is correct |
20 |
Correct |
550 ms |
78564 KB |
Output is correct |
21 |
Correct |
489 ms |
78024 KB |
Output is correct |
22 |
Correct |
160 ms |
48080 KB |
Output is correct |
23 |
Correct |
160 ms |
47092 KB |
Output is correct |
24 |
Correct |
139 ms |
47820 KB |
Output is correct |
25 |
Correct |
143 ms |
47820 KB |
Output is correct |
26 |
Correct |
155 ms |
47580 KB |
Output is correct |
27 |
Correct |
179 ms |
50408 KB |
Output is correct |
28 |
Correct |
164 ms |
47948 KB |
Output is correct |
29 |
Correct |
179 ms |
49756 KB |
Output is correct |
30 |
Correct |
146 ms |
47820 KB |
Output is correct |
31 |
Correct |
191 ms |
50028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5484 KB |
Output is correct |
3 |
Correct |
6 ms |
5484 KB |
Output is correct |
4 |
Correct |
3 ms |
5100 KB |
Output is correct |
5 |
Correct |
5 ms |
5612 KB |
Output is correct |
6 |
Correct |
4 ms |
5484 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
4 ms |
5100 KB |
Output is correct |
9 |
Correct |
5 ms |
5484 KB |
Output is correct |
10 |
Correct |
5 ms |
5484 KB |
Output is correct |
11 |
Correct |
5 ms |
5504 KB |
Output is correct |
12 |
Correct |
6 ms |
5484 KB |
Output is correct |
13 |
Correct |
5 ms |
5484 KB |
Output is correct |
14 |
Correct |
5 ms |
5484 KB |
Output is correct |
15 |
Correct |
5 ms |
5484 KB |
Output is correct |
16 |
Correct |
239 ms |
40976 KB |
Output is correct |
17 |
Correct |
666 ms |
78792 KB |
Output is correct |
18 |
Correct |
40 ms |
13172 KB |
Output is correct |
19 |
Correct |
193 ms |
48716 KB |
Output is correct |
20 |
Correct |
639 ms |
78768 KB |
Output is correct |
21 |
Correct |
346 ms |
57940 KB |
Output is correct |
22 |
Correct |
244 ms |
52080 KB |
Output is correct |
23 |
Correct |
621 ms |
78756 KB |
Output is correct |
24 |
Correct |
618 ms |
78768 KB |
Output is correct |
25 |
Correct |
641 ms |
78748 KB |
Output is correct |
26 |
Correct |
200 ms |
48340 KB |
Output is correct |
27 |
Correct |
200 ms |
48460 KB |
Output is correct |
28 |
Correct |
195 ms |
48332 KB |
Output is correct |
29 |
Correct |
229 ms |
48588 KB |
Output is correct |
30 |
Correct |
210 ms |
48616 KB |
Output is correct |
31 |
Correct |
4 ms |
5100 KB |
Output is correct |
32 |
Correct |
4 ms |
5120 KB |
Output is correct |
33 |
Correct |
4 ms |
5100 KB |
Output is correct |
34 |
Correct |
3 ms |
5100 KB |
Output is correct |
35 |
Correct |
4 ms |
5100 KB |
Output is correct |
36 |
Correct |
4 ms |
5100 KB |
Output is correct |
37 |
Correct |
4 ms |
5100 KB |
Output is correct |
38 |
Correct |
4 ms |
5100 KB |
Output is correct |
39 |
Correct |
4 ms |
5100 KB |
Output is correct |
40 |
Correct |
4 ms |
5100 KB |
Output is correct |
41 |
Correct |
294 ms |
56276 KB |
Output is correct |
42 |
Correct |
561 ms |
78524 KB |
Output is correct |
43 |
Correct |
533 ms |
78748 KB |
Output is correct |
44 |
Correct |
167 ms |
49084 KB |
Output is correct |
45 |
Correct |
553 ms |
78536 KB |
Output is correct |
46 |
Correct |
616 ms |
78600 KB |
Output is correct |
47 |
Correct |
532 ms |
78792 KB |
Output is correct |
48 |
Correct |
564 ms |
78764 KB |
Output is correct |
49 |
Correct |
551 ms |
78576 KB |
Output is correct |
50 |
Correct |
546 ms |
78596 KB |
Output is correct |
51 |
Correct |
564 ms |
78668 KB |
Output is correct |
52 |
Correct |
558 ms |
78536 KB |
Output is correct |
53 |
Correct |
550 ms |
78536 KB |
Output is correct |
54 |
Correct |
540 ms |
78536 KB |
Output is correct |
55 |
Correct |
550 ms |
80840 KB |
Output is correct |
56 |
Correct |
536 ms |
78672 KB |
Output is correct |
57 |
Correct |
586 ms |
78568 KB |
Output is correct |
58 |
Correct |
531 ms |
78536 KB |
Output is correct |
59 |
Correct |
158 ms |
50652 KB |
Output is correct |
60 |
Correct |
550 ms |
78564 KB |
Output is correct |
61 |
Correct |
489 ms |
78024 KB |
Output is correct |
62 |
Correct |
160 ms |
48080 KB |
Output is correct |
63 |
Correct |
160 ms |
47092 KB |
Output is correct |
64 |
Correct |
139 ms |
47820 KB |
Output is correct |
65 |
Correct |
143 ms |
47820 KB |
Output is correct |
66 |
Correct |
155 ms |
47580 KB |
Output is correct |
67 |
Correct |
179 ms |
50408 KB |
Output is correct |
68 |
Correct |
164 ms |
47948 KB |
Output is correct |
69 |
Correct |
179 ms |
49756 KB |
Output is correct |
70 |
Correct |
146 ms |
47820 KB |
Output is correct |
71 |
Correct |
191 ms |
50028 KB |
Output is correct |
72 |
Correct |
384 ms |
56916 KB |
Output is correct |
73 |
Correct |
666 ms |
78500 KB |
Output is correct |
74 |
Correct |
653 ms |
78516 KB |
Output is correct |
75 |
Correct |
613 ms |
78536 KB |
Output is correct |
76 |
Correct |
612 ms |
78536 KB |
Output is correct |
77 |
Correct |
701 ms |
78408 KB |
Output is correct |
78 |
Correct |
661 ms |
78536 KB |
Output is correct |
79 |
Correct |
637 ms |
78664 KB |
Output is correct |
80 |
Correct |
626 ms |
78528 KB |
Output is correct |
81 |
Correct |
628 ms |
78532 KB |
Output is correct |
82 |
Correct |
642 ms |
78536 KB |
Output is correct |
83 |
Correct |
644 ms |
78540 KB |
Output is correct |
84 |
Correct |
651 ms |
78408 KB |
Output is correct |
85 |
Correct |
623 ms |
80596 KB |
Output is correct |
86 |
Correct |
714 ms |
78564 KB |
Output is correct |
87 |
Correct |
660 ms |
78536 KB |
Output is correct |
88 |
Correct |
640 ms |
78536 KB |
Output is correct |
89 |
Correct |
336 ms |
50780 KB |
Output is correct |
90 |
Correct |
651 ms |
78520 KB |
Output is correct |
91 |
Correct |
574 ms |
77640 KB |
Output is correct |
92 |
Correct |
208 ms |
48204 KB |
Output is correct |
93 |
Correct |
272 ms |
47964 KB |
Output is correct |
94 |
Correct |
211 ms |
48204 KB |
Output is correct |
95 |
Correct |
216 ms |
48364 KB |
Output is correct |
96 |
Correct |
268 ms |
48260 KB |
Output is correct |
97 |
Correct |
352 ms |
49884 KB |
Output is correct |
98 |
Correct |
213 ms |
48076 KB |
Output is correct |
99 |
Correct |
362 ms |
51164 KB |
Output is correct |
100 |
Correct |
215 ms |
48200 KB |
Output is correct |