#include<bits/stdc++.h>
using namespace std ;
const int N = 5e5 + 7 ;
int n , m , k , q ;
bool bad[N] , good[N] , viz[N];
int root ;
vector<pair<int , int > > adj[N] ;
vector<int> qrs[N] , tree[N];
priority_queue<pair<int , int > > Q;
int d[N] , ans[N];
vector<int> v ;
vector<pair<int , int > > prs ;
struct DSU{
vector<int> fat ;
void init(int n){
fat.resize(n + 1 ) ;
for(int i = 0 ; i < n ; i++){
fat[i] = i ;
}
}
int fin(int x){
return fat[x] = (fat[x]==x?x:fin(fat[x])) ;
}
void unio(int a, int b){
int aa = fin(a) ;
int bb = fin(b) ;
if(aa!=bb){
fat[aa] = bb ;
}
}
} d1 , d2;
void dijkstra(){
memset(d , -1 , sizeof d) ;
for(auto u : v){
d[u] = 0 ;
}
while(Q.size()){
int dst = -Q.top().first ;
int node = Q.top().second ;
Q.pop() ;
for(auto u : adj[node]){
if(d[u.first]==-1 || dst + u.second < d[u.first]){
d[u.first] = dst + u.second ;
Q.push({-d[u.first] , u.first}) ;
}
}
}
}
int B , t , limit;
int vis[N] ;
vector<pair<int , int > > node ;
int dfs(int x){
if(vis[x]==t)
return 0 ;
vis[x] = t ;
for(auto u : adj[x])
{
if(d[u.first] >=limit && vis[u.first] !=t)
dfs(u.first);
}
}
map<pair<int , int > , bool > mp ;
map<pair<int , int > , int > sol ;
int cur ;
void dfs_lca(int x , int p ){
viz[x] = 1 ;
for(auto u : qrs[x]){
if(viz[u] && mp[{x ,u}]==0){
int lca = d2.fin(u) ;
mp[{x , u}] = mp[{u , x}] = 1 ;
sol[{x , u}] = sol[{u , x}] = d[lca] ;
}
}
for(auto u : tree[x]){
if(u==p)
continue ;
dfs_lca(u ,x ) ;
d2.unio(u , x) ;
}
}
int main(){
cin>>n >>m;
for(int i = 0 ; i < m ; i++){
int a , b, c;
cin>>a>>b>>c ;
adj[a].push_back({b , c}) ;
adj[b].push_back({a , c}) ;
}
cin>>k ;
for(int i = 0 ; i <k ; i++){
int a ;
cin>>a ;
bad[a] = 1 ;
v.push_back(a) ;
Q.push({0 , a}) ;
}
dijkstra() ;
cin>>q ;
for(int i = 0 ; i < q ; i++){
int a, b ;
cin>>a>>b ;
prs.push_back({a ,b }) ;
qrs[a].push_back(b) ;
qrs[b].push_back(a) ;
}
for(int i = 1 ; i <=n ; i++){
node.push_back({-d[i] , i}) ;
}
sort(node.begin() , node.end()) ;
d1.init(N) ;
for(auto u : node){
int nod = u.second ;
int val = -u.first ;
int home = d1.fin(nod) ;
good[nod] = 1 ;
ans[home] = val ;
for(auto it : adj[nod]){
if(good[it.first]){
int fn = d1.fin(it.first) ;
if(fn!=home){
if(ans[fn] < ans[home])
d1.unio(home , fn) ;
else
d1.unio(fn , home) ;
tree[fn].push_back(home) ;
tree[home].push_back(fn) ;
}
}
}
root = nod ;
}
d2.init(N) ;
dfs_lca(root , root) ;
for(int i = 0 ; i < q ; i++){
cout<<sol[prs[i]]<<"\n";
}
return 0 ;
}
Compilation message
plan.cpp: In function 'int dfs(int)':
plan.cpp:76:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
41464 KB |
Output is correct |
2 |
Correct |
33 ms |
41848 KB |
Output is correct |
3 |
Correct |
34 ms |
41852 KB |
Output is correct |
4 |
Correct |
29 ms |
41468 KB |
Output is correct |
5 |
Correct |
33 ms |
41848 KB |
Output is correct |
6 |
Correct |
34 ms |
41848 KB |
Output is correct |
7 |
Correct |
30 ms |
41464 KB |
Output is correct |
8 |
Correct |
30 ms |
41464 KB |
Output is correct |
9 |
Correct |
34 ms |
41848 KB |
Output is correct |
10 |
Correct |
33 ms |
41976 KB |
Output is correct |
11 |
Correct |
34 ms |
41848 KB |
Output is correct |
12 |
Correct |
32 ms |
41852 KB |
Output is correct |
13 |
Correct |
33 ms |
41848 KB |
Output is correct |
14 |
Correct |
34 ms |
41848 KB |
Output is correct |
15 |
Correct |
33 ms |
41848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
41464 KB |
Output is correct |
2 |
Correct |
33 ms |
41848 KB |
Output is correct |
3 |
Correct |
34 ms |
41852 KB |
Output is correct |
4 |
Correct |
29 ms |
41468 KB |
Output is correct |
5 |
Correct |
33 ms |
41848 KB |
Output is correct |
6 |
Correct |
34 ms |
41848 KB |
Output is correct |
7 |
Correct |
30 ms |
41464 KB |
Output is correct |
8 |
Correct |
30 ms |
41464 KB |
Output is correct |
9 |
Correct |
34 ms |
41848 KB |
Output is correct |
10 |
Correct |
33 ms |
41976 KB |
Output is correct |
11 |
Correct |
34 ms |
41848 KB |
Output is correct |
12 |
Correct |
32 ms |
41852 KB |
Output is correct |
13 |
Correct |
33 ms |
41848 KB |
Output is correct |
14 |
Correct |
34 ms |
41848 KB |
Output is correct |
15 |
Correct |
33 ms |
41848 KB |
Output is correct |
16 |
Correct |
745 ms |
82924 KB |
Output is correct |
17 |
Correct |
1535 ms |
103600 KB |
Output is correct |
18 |
Correct |
123 ms |
48248 KB |
Output is correct |
19 |
Correct |
723 ms |
81336 KB |
Output is correct |
20 |
Correct |
1531 ms |
103464 KB |
Output is correct |
21 |
Correct |
956 ms |
92696 KB |
Output is correct |
22 |
Correct |
684 ms |
96616 KB |
Output is correct |
23 |
Correct |
1525 ms |
103472 KB |
Output is correct |
24 |
Correct |
1545 ms |
103592 KB |
Output is correct |
25 |
Correct |
1560 ms |
103464 KB |
Output is correct |
26 |
Correct |
696 ms |
81396 KB |
Output is correct |
27 |
Correct |
713 ms |
81388 KB |
Output is correct |
28 |
Correct |
687 ms |
81260 KB |
Output is correct |
29 |
Correct |
676 ms |
81376 KB |
Output is correct |
30 |
Correct |
695 ms |
81384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
41464 KB |
Output is correct |
2 |
Correct |
30 ms |
41464 KB |
Output is correct |
3 |
Correct |
30 ms |
41464 KB |
Output is correct |
4 |
Correct |
30 ms |
41464 KB |
Output is correct |
5 |
Correct |
31 ms |
41464 KB |
Output is correct |
6 |
Correct |
31 ms |
41464 KB |
Output is correct |
7 |
Correct |
29 ms |
41464 KB |
Output is correct |
8 |
Correct |
30 ms |
41464 KB |
Output is correct |
9 |
Correct |
30 ms |
41464 KB |
Output is correct |
10 |
Correct |
31 ms |
41464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
465 ms |
63340 KB |
Output is correct |
2 |
Correct |
1000 ms |
74896 KB |
Output is correct |
3 |
Correct |
982 ms |
74852 KB |
Output is correct |
4 |
Correct |
227 ms |
59368 KB |
Output is correct |
5 |
Correct |
1020 ms |
74860 KB |
Output is correct |
6 |
Correct |
1008 ms |
75016 KB |
Output is correct |
7 |
Correct |
1040 ms |
74988 KB |
Output is correct |
8 |
Correct |
996 ms |
74856 KB |
Output is correct |
9 |
Correct |
1008 ms |
74864 KB |
Output is correct |
10 |
Correct |
970 ms |
74924 KB |
Output is correct |
11 |
Correct |
973 ms |
74856 KB |
Output is correct |
12 |
Correct |
1006 ms |
74984 KB |
Output is correct |
13 |
Correct |
983 ms |
74992 KB |
Output is correct |
14 |
Correct |
994 ms |
75004 KB |
Output is correct |
15 |
Correct |
982 ms |
75112 KB |
Output is correct |
16 |
Correct |
999 ms |
74996 KB |
Output is correct |
17 |
Correct |
972 ms |
74984 KB |
Output is correct |
18 |
Correct |
991 ms |
74908 KB |
Output is correct |
19 |
Correct |
225 ms |
67176 KB |
Output is correct |
20 |
Correct |
983 ms |
74728 KB |
Output is correct |
21 |
Correct |
950 ms |
74992 KB |
Output is correct |
22 |
Correct |
225 ms |
51808 KB |
Output is correct |
23 |
Correct |
242 ms |
53864 KB |
Output is correct |
24 |
Correct |
224 ms |
52084 KB |
Output is correct |
25 |
Correct |
225 ms |
51820 KB |
Output is correct |
26 |
Correct |
246 ms |
51308 KB |
Output is correct |
27 |
Correct |
220 ms |
59248 KB |
Output is correct |
28 |
Correct |
225 ms |
52068 KB |
Output is correct |
29 |
Correct |
220 ms |
59244 KB |
Output is correct |
30 |
Correct |
224 ms |
51932 KB |
Output is correct |
31 |
Correct |
218 ms |
59244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
41464 KB |
Output is correct |
2 |
Correct |
33 ms |
41848 KB |
Output is correct |
3 |
Correct |
34 ms |
41852 KB |
Output is correct |
4 |
Correct |
29 ms |
41468 KB |
Output is correct |
5 |
Correct |
33 ms |
41848 KB |
Output is correct |
6 |
Correct |
34 ms |
41848 KB |
Output is correct |
7 |
Correct |
30 ms |
41464 KB |
Output is correct |
8 |
Correct |
30 ms |
41464 KB |
Output is correct |
9 |
Correct |
34 ms |
41848 KB |
Output is correct |
10 |
Correct |
33 ms |
41976 KB |
Output is correct |
11 |
Correct |
34 ms |
41848 KB |
Output is correct |
12 |
Correct |
32 ms |
41852 KB |
Output is correct |
13 |
Correct |
33 ms |
41848 KB |
Output is correct |
14 |
Correct |
34 ms |
41848 KB |
Output is correct |
15 |
Correct |
33 ms |
41848 KB |
Output is correct |
16 |
Correct |
745 ms |
82924 KB |
Output is correct |
17 |
Correct |
1535 ms |
103600 KB |
Output is correct |
18 |
Correct |
123 ms |
48248 KB |
Output is correct |
19 |
Correct |
723 ms |
81336 KB |
Output is correct |
20 |
Correct |
1531 ms |
103464 KB |
Output is correct |
21 |
Correct |
956 ms |
92696 KB |
Output is correct |
22 |
Correct |
684 ms |
96616 KB |
Output is correct |
23 |
Correct |
1525 ms |
103472 KB |
Output is correct |
24 |
Correct |
1545 ms |
103592 KB |
Output is correct |
25 |
Correct |
1560 ms |
103464 KB |
Output is correct |
26 |
Correct |
696 ms |
81396 KB |
Output is correct |
27 |
Correct |
713 ms |
81388 KB |
Output is correct |
28 |
Correct |
687 ms |
81260 KB |
Output is correct |
29 |
Correct |
676 ms |
81376 KB |
Output is correct |
30 |
Correct |
695 ms |
81384 KB |
Output is correct |
31 |
Correct |
31 ms |
41464 KB |
Output is correct |
32 |
Correct |
30 ms |
41464 KB |
Output is correct |
33 |
Correct |
30 ms |
41464 KB |
Output is correct |
34 |
Correct |
30 ms |
41464 KB |
Output is correct |
35 |
Correct |
31 ms |
41464 KB |
Output is correct |
36 |
Correct |
31 ms |
41464 KB |
Output is correct |
37 |
Correct |
29 ms |
41464 KB |
Output is correct |
38 |
Correct |
30 ms |
41464 KB |
Output is correct |
39 |
Correct |
30 ms |
41464 KB |
Output is correct |
40 |
Correct |
31 ms |
41464 KB |
Output is correct |
41 |
Correct |
465 ms |
63340 KB |
Output is correct |
42 |
Correct |
1000 ms |
74896 KB |
Output is correct |
43 |
Correct |
982 ms |
74852 KB |
Output is correct |
44 |
Correct |
227 ms |
59368 KB |
Output is correct |
45 |
Correct |
1020 ms |
74860 KB |
Output is correct |
46 |
Correct |
1008 ms |
75016 KB |
Output is correct |
47 |
Correct |
1040 ms |
74988 KB |
Output is correct |
48 |
Correct |
996 ms |
74856 KB |
Output is correct |
49 |
Correct |
1008 ms |
74864 KB |
Output is correct |
50 |
Correct |
970 ms |
74924 KB |
Output is correct |
51 |
Correct |
973 ms |
74856 KB |
Output is correct |
52 |
Correct |
1006 ms |
74984 KB |
Output is correct |
53 |
Correct |
983 ms |
74992 KB |
Output is correct |
54 |
Correct |
994 ms |
75004 KB |
Output is correct |
55 |
Correct |
982 ms |
75112 KB |
Output is correct |
56 |
Correct |
999 ms |
74996 KB |
Output is correct |
57 |
Correct |
972 ms |
74984 KB |
Output is correct |
58 |
Correct |
991 ms |
74908 KB |
Output is correct |
59 |
Correct |
225 ms |
67176 KB |
Output is correct |
60 |
Correct |
983 ms |
74728 KB |
Output is correct |
61 |
Correct |
950 ms |
74992 KB |
Output is correct |
62 |
Correct |
225 ms |
51808 KB |
Output is correct |
63 |
Correct |
242 ms |
53864 KB |
Output is correct |
64 |
Correct |
224 ms |
52084 KB |
Output is correct |
65 |
Correct |
225 ms |
51820 KB |
Output is correct |
66 |
Correct |
246 ms |
51308 KB |
Output is correct |
67 |
Correct |
220 ms |
59248 KB |
Output is correct |
68 |
Correct |
225 ms |
52068 KB |
Output is correct |
69 |
Correct |
220 ms |
59244 KB |
Output is correct |
70 |
Correct |
224 ms |
51932 KB |
Output is correct |
71 |
Correct |
218 ms |
59244 KB |
Output is correct |
72 |
Correct |
1027 ms |
93096 KB |
Output is correct |
73 |
Correct |
1491 ms |
112304 KB |
Output is correct |
74 |
Correct |
1515 ms |
112300 KB |
Output is correct |
75 |
Correct |
1529 ms |
112312 KB |
Output is correct |
76 |
Correct |
1514 ms |
112424 KB |
Output is correct |
77 |
Correct |
1493 ms |
112300 KB |
Output is correct |
78 |
Correct |
1483 ms |
112392 KB |
Output is correct |
79 |
Correct |
1499 ms |
112392 KB |
Output is correct |
80 |
Correct |
1501 ms |
112296 KB |
Output is correct |
81 |
Correct |
1516 ms |
112300 KB |
Output is correct |
82 |
Correct |
1535 ms |
112428 KB |
Output is correct |
83 |
Correct |
1528 ms |
112396 KB |
Output is correct |
84 |
Correct |
1524 ms |
112448 KB |
Output is correct |
85 |
Correct |
1572 ms |
112440 KB |
Output is correct |
86 |
Correct |
1501 ms |
112424 KB |
Output is correct |
87 |
Correct |
1509 ms |
112392 KB |
Output is correct |
88 |
Correct |
1539 ms |
112420 KB |
Output is correct |
89 |
Correct |
754 ms |
98764 KB |
Output is correct |
90 |
Correct |
1499 ms |
112256 KB |
Output is correct |
91 |
Correct |
1475 ms |
112844 KB |
Output is correct |
92 |
Correct |
748 ms |
82932 KB |
Output is correct |
93 |
Correct |
744 ms |
85352 KB |
Output is correct |
94 |
Correct |
732 ms |
83068 KB |
Output is correct |
95 |
Correct |
729 ms |
82936 KB |
Output is correct |
96 |
Correct |
726 ms |
82408 KB |
Output is correct |
97 |
Correct |
715 ms |
89708 KB |
Output is correct |
98 |
Correct |
742 ms |
83064 KB |
Output is correct |
99 |
Correct |
739 ms |
89780 KB |
Output is correct |
100 |
Correct |
761 ms |
83064 KB |
Output is correct |