#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define mid(l, r) ((l)+(r))/2
#define len(a) (a).length()
#define sz(a) (a).size()
#define xx first
#define yy second
#define inf int(2e9)
#define ff(i, a, b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i, a, b) for(int (i) = (a); (i) >= (b); --(i))
#define maxn 200005
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class T>
void print(const T niz[], const int siz)
{
for(int i=0;i<siz;i++)
cout << niz[i] << " ";
cout << endl;
}
struct edge{
int x;
int y;
int w;
};
bool cmp(edge a, edge b){
return a.w > b.w;
}
int n, m, k;
vector<pii>graf[maxn];
int dist[maxn];
bool mark[maxn];
vector<int>koji;
bool bio[maxn];
vector<edge>e1;
vector<edge>e2;
vector<edge>chosen;
void djikstra(){
priority_queue<pii, vector<pii>, greater<pii>>pq;
for(auto c:koji)pq.push({0, c});
while(!pq.empty()){
pii tr = pq.top();
pq.pop();
dist[tr.yy] = min(tr.xx, dist[tr.yy]);
for(auto c:graf[tr.yy]){
if(dist[c.xx] > dist[tr.yy] + c.yy){
dist[c.xx] = dist[tr.yy] + c.yy;
pq.push({dist[tr.yy] + c.yy, c.xx});
}
}
}
}
int dsu[maxn];
int findpar(int x){
if(x == dsu[x])return x;
return dsu[x] = findpar(dsu[x]);
}
void init(){
ff(i,1,n)dsu[i] = i;
}
bool spojeni(int x, int y){
return findpar(x) == findpar(y);
}
void unite(int x, int y){
int a = findpar(x);
int b = findpar(y);
if(a == b)return;
dsu[a] = b;
}
vector<pii> mst[maxn];
int deb[maxn];
int lca[maxn][20];
int par[maxn][20];
int in[maxn];
int out[maxn];
int br;
void root(int x, int pret, int dub, int val){
deb[x] = dub;
in[x] = br++;
par[x][0] = pret;
for(int i=1; i<18; i++){
par[x][i] = par[par[x][i - 1]][i - 1];
}
lca[x][0] = val;
for(int i=1; i<18; i++){
lca[x][i] = min(lca[x][i - 1], lca[par[x][i - 1]][i - 1]);
}
for(auto c:mst[x]){
if(c.xx == pret)continue;
root(c.xx, x, dub + 1, c.yy);
}
out[x] = br;
}
bool insubtr(int x, int y){
/// y u x
if(x == 0)return 1;
if(in[y] > in[x] && in[y] < out[x])return 1;
return 0;
}
int ancestor(int x, int y){
if(x == y)return x;
if(insubtr(x, y))return x;
if(insubtr(y, x))return y;
for(int i=17; i>=0; i--){
if(!insubtr(par[x][i], y))x = par[x][i];
}
return par[x][0];
}
int res(int x, int cale){
int res = 1e9;
for(int i=17; i>=0; i--){
if(par[x][i] == cale){
res = min(res, lca[x][i]);
return res;
}
if(!insubtr(par[x][i], cale)){
res = min(res, lca[x][i]);
x = par[x][i];
}
}
return res;
}
int upit(int x, int y){
int cale = ancestor(x, y);
return min(res(x, cale), res(y, cale));
}
int main()
{
ios_base::sync_with_stdio(false);
cin >> n >> m;
ff(i,0,m - 1){
int x,y,z; cin >> x >> y >> z;
graf[x].pb({y,z}); graf[y].pb({x,z});
e1.pb({x,y,z});
}
ff(i,1,n)dist[i] = 1e9;
cin >> k;
ff(i,0,k - 1){
int x;
cin >> x;
mark[x] = 1;
koji.pb(x);
}
djikstra();
init();
for(auto c:e1){
e2.pb({c.x, c.y, min(dist[c.x], dist[c.y])});
}
sort(e2.begin(), e2.end(), cmp);
for(auto c:e2){
int prvi = c.x;
int drugi = c.y;
if(spojeni(prvi,drugi))continue;
unite(prvi, drugi);
chosen.pb(c);
mst[c.x].pb({c.y, c.w});
mst[c.y].pb({c.x, c.w});
}
root(1,0,0,1e9);
int q;
cin >> q;
while(q -- ){
int a,b;
cin >> a >> b;
cout << upit(a, b) << endl;
//dfs(a,0,dist[a]);
//cout << res[b] << endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9724 KB |
Output is correct |
2 |
Correct |
14 ms |
10104 KB |
Output is correct |
3 |
Correct |
14 ms |
10104 KB |
Output is correct |
4 |
Correct |
10 ms |
9720 KB |
Output is correct |
5 |
Correct |
14 ms |
10104 KB |
Output is correct |
6 |
Correct |
14 ms |
10104 KB |
Output is correct |
7 |
Correct |
10 ms |
9848 KB |
Output is correct |
8 |
Correct |
10 ms |
9848 KB |
Output is correct |
9 |
Correct |
14 ms |
10232 KB |
Output is correct |
10 |
Correct |
15 ms |
10104 KB |
Output is correct |
11 |
Correct |
14 ms |
10104 KB |
Output is correct |
12 |
Correct |
14 ms |
10104 KB |
Output is correct |
13 |
Correct |
14 ms |
10104 KB |
Output is correct |
14 |
Correct |
14 ms |
10076 KB |
Output is correct |
15 |
Correct |
14 ms |
10104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9724 KB |
Output is correct |
2 |
Correct |
14 ms |
10104 KB |
Output is correct |
3 |
Correct |
14 ms |
10104 KB |
Output is correct |
4 |
Correct |
10 ms |
9720 KB |
Output is correct |
5 |
Correct |
14 ms |
10104 KB |
Output is correct |
6 |
Correct |
14 ms |
10104 KB |
Output is correct |
7 |
Correct |
10 ms |
9848 KB |
Output is correct |
8 |
Correct |
10 ms |
9848 KB |
Output is correct |
9 |
Correct |
14 ms |
10232 KB |
Output is correct |
10 |
Correct |
15 ms |
10104 KB |
Output is correct |
11 |
Correct |
14 ms |
10104 KB |
Output is correct |
12 |
Correct |
14 ms |
10104 KB |
Output is correct |
13 |
Correct |
14 ms |
10104 KB |
Output is correct |
14 |
Correct |
14 ms |
10076 KB |
Output is correct |
15 |
Correct |
14 ms |
10104 KB |
Output is correct |
16 |
Correct |
512 ms |
36316 KB |
Output is correct |
17 |
Correct |
940 ms |
61812 KB |
Output is correct |
18 |
Correct |
82 ms |
15404 KB |
Output is correct |
19 |
Correct |
474 ms |
40544 KB |
Output is correct |
20 |
Correct |
943 ms |
59884 KB |
Output is correct |
21 |
Correct |
647 ms |
44988 KB |
Output is correct |
22 |
Correct |
537 ms |
47144 KB |
Output is correct |
23 |
Correct |
940 ms |
60092 KB |
Output is correct |
24 |
Correct |
949 ms |
60152 KB |
Output is correct |
25 |
Correct |
952 ms |
61872 KB |
Output is correct |
26 |
Correct |
477 ms |
40880 KB |
Output is correct |
27 |
Correct |
476 ms |
42356 KB |
Output is correct |
28 |
Correct |
490 ms |
42172 KB |
Output is correct |
29 |
Correct |
475 ms |
42248 KB |
Output is correct |
30 |
Correct |
479 ms |
42280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9720 KB |
Output is correct |
2 |
Correct |
10 ms |
9720 KB |
Output is correct |
3 |
Correct |
10 ms |
9720 KB |
Output is correct |
4 |
Correct |
10 ms |
9720 KB |
Output is correct |
5 |
Correct |
10 ms |
9840 KB |
Output is correct |
6 |
Correct |
10 ms |
9720 KB |
Output is correct |
7 |
Correct |
10 ms |
9720 KB |
Output is correct |
8 |
Correct |
10 ms |
9848 KB |
Output is correct |
9 |
Correct |
10 ms |
9720 KB |
Output is correct |
10 |
Correct |
10 ms |
9848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
299 ms |
44492 KB |
Output is correct |
2 |
Correct |
616 ms |
57376 KB |
Output is correct |
3 |
Correct |
629 ms |
57236 KB |
Output is correct |
4 |
Correct |
220 ms |
42664 KB |
Output is correct |
5 |
Correct |
626 ms |
57356 KB |
Output is correct |
6 |
Correct |
636 ms |
57356 KB |
Output is correct |
7 |
Correct |
602 ms |
57396 KB |
Output is correct |
8 |
Correct |
639 ms |
57536 KB |
Output is correct |
9 |
Correct |
705 ms |
57400 KB |
Output is correct |
10 |
Correct |
628 ms |
57296 KB |
Output is correct |
11 |
Correct |
651 ms |
57372 KB |
Output is correct |
12 |
Correct |
641 ms |
57316 KB |
Output is correct |
13 |
Correct |
630 ms |
57360 KB |
Output is correct |
14 |
Correct |
616 ms |
57336 KB |
Output is correct |
15 |
Correct |
652 ms |
57208 KB |
Output is correct |
16 |
Correct |
661 ms |
57360 KB |
Output is correct |
17 |
Correct |
615 ms |
57416 KB |
Output is correct |
18 |
Correct |
619 ms |
57168 KB |
Output is correct |
19 |
Correct |
184 ms |
44068 KB |
Output is correct |
20 |
Correct |
591 ms |
57348 KB |
Output is correct |
21 |
Correct |
604 ms |
60456 KB |
Output is correct |
22 |
Correct |
155 ms |
39944 KB |
Output is correct |
23 |
Correct |
172 ms |
39660 KB |
Output is correct |
24 |
Correct |
154 ms |
39956 KB |
Output is correct |
25 |
Correct |
162 ms |
39980 KB |
Output is correct |
26 |
Correct |
181 ms |
40104 KB |
Output is correct |
27 |
Correct |
195 ms |
43684 KB |
Output is correct |
28 |
Correct |
150 ms |
39952 KB |
Output is correct |
29 |
Correct |
192 ms |
42832 KB |
Output is correct |
30 |
Correct |
158 ms |
39980 KB |
Output is correct |
31 |
Correct |
196 ms |
42920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9724 KB |
Output is correct |
2 |
Correct |
14 ms |
10104 KB |
Output is correct |
3 |
Correct |
14 ms |
10104 KB |
Output is correct |
4 |
Correct |
10 ms |
9720 KB |
Output is correct |
5 |
Correct |
14 ms |
10104 KB |
Output is correct |
6 |
Correct |
14 ms |
10104 KB |
Output is correct |
7 |
Correct |
10 ms |
9848 KB |
Output is correct |
8 |
Correct |
10 ms |
9848 KB |
Output is correct |
9 |
Correct |
14 ms |
10232 KB |
Output is correct |
10 |
Correct |
15 ms |
10104 KB |
Output is correct |
11 |
Correct |
14 ms |
10104 KB |
Output is correct |
12 |
Correct |
14 ms |
10104 KB |
Output is correct |
13 |
Correct |
14 ms |
10104 KB |
Output is correct |
14 |
Correct |
14 ms |
10076 KB |
Output is correct |
15 |
Correct |
14 ms |
10104 KB |
Output is correct |
16 |
Correct |
512 ms |
36316 KB |
Output is correct |
17 |
Correct |
940 ms |
61812 KB |
Output is correct |
18 |
Correct |
82 ms |
15404 KB |
Output is correct |
19 |
Correct |
474 ms |
40544 KB |
Output is correct |
20 |
Correct |
943 ms |
59884 KB |
Output is correct |
21 |
Correct |
647 ms |
44988 KB |
Output is correct |
22 |
Correct |
537 ms |
47144 KB |
Output is correct |
23 |
Correct |
940 ms |
60092 KB |
Output is correct |
24 |
Correct |
949 ms |
60152 KB |
Output is correct |
25 |
Correct |
952 ms |
61872 KB |
Output is correct |
26 |
Correct |
477 ms |
40880 KB |
Output is correct |
27 |
Correct |
476 ms |
42356 KB |
Output is correct |
28 |
Correct |
490 ms |
42172 KB |
Output is correct |
29 |
Correct |
475 ms |
42248 KB |
Output is correct |
30 |
Correct |
479 ms |
42280 KB |
Output is correct |
31 |
Correct |
10 ms |
9720 KB |
Output is correct |
32 |
Correct |
10 ms |
9720 KB |
Output is correct |
33 |
Correct |
10 ms |
9720 KB |
Output is correct |
34 |
Correct |
10 ms |
9720 KB |
Output is correct |
35 |
Correct |
10 ms |
9840 KB |
Output is correct |
36 |
Correct |
10 ms |
9720 KB |
Output is correct |
37 |
Correct |
10 ms |
9720 KB |
Output is correct |
38 |
Correct |
10 ms |
9848 KB |
Output is correct |
39 |
Correct |
10 ms |
9720 KB |
Output is correct |
40 |
Correct |
10 ms |
9848 KB |
Output is correct |
41 |
Correct |
299 ms |
44492 KB |
Output is correct |
42 |
Correct |
616 ms |
57376 KB |
Output is correct |
43 |
Correct |
629 ms |
57236 KB |
Output is correct |
44 |
Correct |
220 ms |
42664 KB |
Output is correct |
45 |
Correct |
626 ms |
57356 KB |
Output is correct |
46 |
Correct |
636 ms |
57356 KB |
Output is correct |
47 |
Correct |
602 ms |
57396 KB |
Output is correct |
48 |
Correct |
639 ms |
57536 KB |
Output is correct |
49 |
Correct |
705 ms |
57400 KB |
Output is correct |
50 |
Correct |
628 ms |
57296 KB |
Output is correct |
51 |
Correct |
651 ms |
57372 KB |
Output is correct |
52 |
Correct |
641 ms |
57316 KB |
Output is correct |
53 |
Correct |
630 ms |
57360 KB |
Output is correct |
54 |
Correct |
616 ms |
57336 KB |
Output is correct |
55 |
Correct |
652 ms |
57208 KB |
Output is correct |
56 |
Correct |
661 ms |
57360 KB |
Output is correct |
57 |
Correct |
615 ms |
57416 KB |
Output is correct |
58 |
Correct |
619 ms |
57168 KB |
Output is correct |
59 |
Correct |
184 ms |
44068 KB |
Output is correct |
60 |
Correct |
591 ms |
57348 KB |
Output is correct |
61 |
Correct |
604 ms |
60456 KB |
Output is correct |
62 |
Correct |
155 ms |
39944 KB |
Output is correct |
63 |
Correct |
172 ms |
39660 KB |
Output is correct |
64 |
Correct |
154 ms |
39956 KB |
Output is correct |
65 |
Correct |
162 ms |
39980 KB |
Output is correct |
66 |
Correct |
181 ms |
40104 KB |
Output is correct |
67 |
Correct |
195 ms |
43684 KB |
Output is correct |
68 |
Correct |
150 ms |
39952 KB |
Output is correct |
69 |
Correct |
192 ms |
42832 KB |
Output is correct |
70 |
Correct |
158 ms |
39980 KB |
Output is correct |
71 |
Correct |
196 ms |
42920 KB |
Output is correct |
72 |
Correct |
648 ms |
44084 KB |
Output is correct |
73 |
Correct |
948 ms |
57628 KB |
Output is correct |
74 |
Correct |
944 ms |
57420 KB |
Output is correct |
75 |
Correct |
958 ms |
57492 KB |
Output is correct |
76 |
Correct |
970 ms |
57484 KB |
Output is correct |
77 |
Correct |
956 ms |
57712 KB |
Output is correct |
78 |
Correct |
977 ms |
57556 KB |
Output is correct |
79 |
Correct |
960 ms |
57604 KB |
Output is correct |
80 |
Correct |
952 ms |
57712 KB |
Output is correct |
81 |
Correct |
1037 ms |
57752 KB |
Output is correct |
82 |
Correct |
1052 ms |
57608 KB |
Output is correct |
83 |
Correct |
981 ms |
57492 KB |
Output is correct |
84 |
Correct |
957 ms |
57560 KB |
Output is correct |
85 |
Correct |
978 ms |
58136 KB |
Output is correct |
86 |
Correct |
958 ms |
60400 KB |
Output is correct |
87 |
Correct |
940 ms |
62732 KB |
Output is correct |
88 |
Correct |
934 ms |
63388 KB |
Output is correct |
89 |
Correct |
584 ms |
45808 KB |
Output is correct |
90 |
Correct |
940 ms |
64780 KB |
Output is correct |
91 |
Correct |
988 ms |
68760 KB |
Output is correct |
92 |
Correct |
501 ms |
42248 KB |
Output is correct |
93 |
Correct |
584 ms |
42612 KB |
Output is correct |
94 |
Correct |
502 ms |
42256 KB |
Output is correct |
95 |
Correct |
493 ms |
42248 KB |
Output is correct |
96 |
Correct |
571 ms |
42936 KB |
Output is correct |
97 |
Correct |
601 ms |
44836 KB |
Output is correct |
98 |
Correct |
503 ms |
42212 KB |
Output is correct |
99 |
Correct |
622 ms |
46448 KB |
Output is correct |
100 |
Correct |
499 ms |
42388 KB |
Output is correct |