#include <iostream>
#include <vector>
#include <memory.h>
#include <unordered_set>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
const int maxn=100010;
vector<pair<int,int>> G[maxn];
int dist[maxn];
int dsu[maxn];
int sz[maxn];
struct DSU{
DSU(int n){
for(int i=1;i<=n;i++)dsu[i]=i,sz[i]=1;
}
int find(int v){
if(dsu[v]==v)return v;
return dsu[v]=find(dsu[v]);
}
void merge(int a,int b){
a=find(a);
b=find(b);
if(a==b)return;
if(sz[a]>sz[b]){
sz[a]+=sz[b];
dsu[b]=a;
}
else{
sz[b]+=sz[a];
dsu[a]=b;
}
}
};
bool added[maxn];
signed main(){
memset(dist,63,sizeof(dist));
ios_base::sync_with_stdio(0);cin.tie(0);
int n; cin>>n;
int m; cin>>m;
for(int i=0;i<m;i++){
int u,v,w; cin>>u>>v>>w;
G[u].emplace_back(v,w);
G[v].emplace_back(u,w);
}
int k; cin>>k;
dist[0]=0;
for(int i=0;i<k;i++){
int x;cin>>x;
G[0].emplace_back(x,0);
}
set<pair<int,int>> dijkstra;
dijkstra.emplace(0,0);
while(dijkstra.size()){
int d=dijkstra.begin()->first;
int v=dijkstra.begin()->second;
dijkstra.erase(dijkstra.begin());
if(d!=dist[v])continue;
for(auto &edge:G[v]){
int u=edge.first;
int w=edge.second;
if(dist[u]>d+w){
dijkstra.erase({dist[u],u});
dist[u]=d+w;
dijkstra.emplace(dist[u],u);
}
}
}
vector<pair<int,int>> vertexes;
for(int v=1;v<=n;v++)vertexes.emplace_back(dist[v],v);
sort(vertexes.rbegin(),vertexes.rend());
int q;
cin>>q;
vector<pair<int,int>> que;
for(int i=0;i<q;i++){
int a,b; cin>>a>>b;
que.emplace_back(a,b);
}
vector<pair<int,int>> bin_search(q);
for(int i=0;i<q;i++)bin_search[i]={0,n-1};
vector<vector<int>>queries(n);
for(int t=0;t<17;t++){
for(int i=0;i<n;i++)queries[i].clear();
for(int i=0;i<q;i++){
int m=(bin_search[i].first+bin_search[i].second)>>1;
queries[m].emplace_back(i);
}
DSU dsu(n);
memset(added,0,sizeof(added));
for(int i=0;i<n;i++){
int cur_v=vertexes[i].second;
for(auto &edge:G[cur_v]){
int u=edge.first;
if(added[u]) dsu.merge(u,cur_v);
}
added[cur_v]=true;
for(auto &query:queries[i]){
int a=que[query].first;
int b=que[query].second;
if(!added[a]||!added[b]){
bin_search[query].first=i;
} else {
if(dsu.find(a)!=dsu.find(b)){
bin_search[query].first=i;
}else{
bin_search[query].second=i;
}
}
}
}
}
for(int i=0;i<q;i++){
cout<<vertexes[bin_search[i].second].first<<"\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3192 KB |
Output is correct |
2 |
Correct |
6 ms |
3320 KB |
Output is correct |
3 |
Correct |
6 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3192 KB |
Output is correct |
5 |
Correct |
6 ms |
3320 KB |
Output is correct |
6 |
Correct |
7 ms |
3340 KB |
Output is correct |
7 |
Correct |
5 ms |
3192 KB |
Output is correct |
8 |
Correct |
5 ms |
3160 KB |
Output is correct |
9 |
Correct |
7 ms |
3448 KB |
Output is correct |
10 |
Correct |
7 ms |
3320 KB |
Output is correct |
11 |
Correct |
7 ms |
3320 KB |
Output is correct |
12 |
Correct |
6 ms |
3320 KB |
Output is correct |
13 |
Correct |
7 ms |
3320 KB |
Output is correct |
14 |
Correct |
7 ms |
3448 KB |
Output is correct |
15 |
Correct |
7 ms |
3320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3192 KB |
Output is correct |
2 |
Correct |
6 ms |
3320 KB |
Output is correct |
3 |
Correct |
6 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3192 KB |
Output is correct |
5 |
Correct |
6 ms |
3320 KB |
Output is correct |
6 |
Correct |
7 ms |
3340 KB |
Output is correct |
7 |
Correct |
5 ms |
3192 KB |
Output is correct |
8 |
Correct |
5 ms |
3160 KB |
Output is correct |
9 |
Correct |
7 ms |
3448 KB |
Output is correct |
10 |
Correct |
7 ms |
3320 KB |
Output is correct |
11 |
Correct |
7 ms |
3320 KB |
Output is correct |
12 |
Correct |
6 ms |
3320 KB |
Output is correct |
13 |
Correct |
7 ms |
3320 KB |
Output is correct |
14 |
Correct |
7 ms |
3448 KB |
Output is correct |
15 |
Correct |
7 ms |
3320 KB |
Output is correct |
16 |
Correct |
559 ms |
24200 KB |
Output is correct |
17 |
Correct |
1374 ms |
41292 KB |
Output is correct |
18 |
Correct |
77 ms |
6672 KB |
Output is correct |
19 |
Correct |
327 ms |
23284 KB |
Output is correct |
20 |
Correct |
1382 ms |
41136 KB |
Output is correct |
21 |
Correct |
769 ms |
29992 KB |
Output is correct |
22 |
Correct |
500 ms |
25728 KB |
Output is correct |
23 |
Correct |
1379 ms |
41092 KB |
Output is correct |
24 |
Correct |
1404 ms |
41240 KB |
Output is correct |
25 |
Correct |
1374 ms |
41208 KB |
Output is correct |
26 |
Correct |
335 ms |
23256 KB |
Output is correct |
27 |
Correct |
310 ms |
22828 KB |
Output is correct |
28 |
Correct |
316 ms |
22952 KB |
Output is correct |
29 |
Correct |
325 ms |
23312 KB |
Output is correct |
30 |
Correct |
305 ms |
23196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3192 KB |
Output is correct |
2 |
Correct |
4 ms |
3192 KB |
Output is correct |
3 |
Correct |
5 ms |
3192 KB |
Output is correct |
4 |
Correct |
5 ms |
3320 KB |
Output is correct |
5 |
Correct |
5 ms |
3148 KB |
Output is correct |
6 |
Correct |
5 ms |
3192 KB |
Output is correct |
7 |
Correct |
4 ms |
3192 KB |
Output is correct |
8 |
Correct |
5 ms |
3192 KB |
Output is correct |
9 |
Correct |
5 ms |
3192 KB |
Output is correct |
10 |
Correct |
4 ms |
3192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
608 ms |
16972 KB |
Output is correct |
2 |
Correct |
1119 ms |
29508 KB |
Output is correct |
3 |
Correct |
1138 ms |
29384 KB |
Output is correct |
4 |
Correct |
324 ms |
12012 KB |
Output is correct |
5 |
Correct |
1132 ms |
29296 KB |
Output is correct |
6 |
Correct |
1125 ms |
29408 KB |
Output is correct |
7 |
Correct |
1125 ms |
29212 KB |
Output is correct |
8 |
Correct |
1166 ms |
29348 KB |
Output is correct |
9 |
Correct |
1167 ms |
29380 KB |
Output is correct |
10 |
Correct |
1137 ms |
29216 KB |
Output is correct |
11 |
Correct |
1128 ms |
29356 KB |
Output is correct |
12 |
Correct |
1128 ms |
29476 KB |
Output is correct |
13 |
Correct |
1117 ms |
29360 KB |
Output is correct |
14 |
Correct |
1100 ms |
29420 KB |
Output is correct |
15 |
Correct |
1111 ms |
29664 KB |
Output is correct |
16 |
Correct |
1136 ms |
29520 KB |
Output is correct |
17 |
Correct |
1120 ms |
29500 KB |
Output is correct |
18 |
Correct |
1144 ms |
29472 KB |
Output is correct |
19 |
Correct |
267 ms |
12008 KB |
Output is correct |
20 |
Correct |
1215 ms |
29448 KB |
Output is correct |
21 |
Correct |
895 ms |
30508 KB |
Output is correct |
22 |
Correct |
215 ms |
13420 KB |
Output is correct |
23 |
Correct |
253 ms |
12648 KB |
Output is correct |
24 |
Correct |
217 ms |
13292 KB |
Output is correct |
25 |
Correct |
223 ms |
13388 KB |
Output is correct |
26 |
Correct |
309 ms |
12620 KB |
Output is correct |
27 |
Correct |
312 ms |
12012 KB |
Output is correct |
28 |
Correct |
230 ms |
13292 KB |
Output is correct |
29 |
Correct |
315 ms |
12084 KB |
Output is correct |
30 |
Correct |
222 ms |
13420 KB |
Output is correct |
31 |
Correct |
272 ms |
12012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3192 KB |
Output is correct |
2 |
Correct |
6 ms |
3320 KB |
Output is correct |
3 |
Correct |
6 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3192 KB |
Output is correct |
5 |
Correct |
6 ms |
3320 KB |
Output is correct |
6 |
Correct |
7 ms |
3340 KB |
Output is correct |
7 |
Correct |
5 ms |
3192 KB |
Output is correct |
8 |
Correct |
5 ms |
3160 KB |
Output is correct |
9 |
Correct |
7 ms |
3448 KB |
Output is correct |
10 |
Correct |
7 ms |
3320 KB |
Output is correct |
11 |
Correct |
7 ms |
3320 KB |
Output is correct |
12 |
Correct |
6 ms |
3320 KB |
Output is correct |
13 |
Correct |
7 ms |
3320 KB |
Output is correct |
14 |
Correct |
7 ms |
3448 KB |
Output is correct |
15 |
Correct |
7 ms |
3320 KB |
Output is correct |
16 |
Correct |
559 ms |
24200 KB |
Output is correct |
17 |
Correct |
1374 ms |
41292 KB |
Output is correct |
18 |
Correct |
77 ms |
6672 KB |
Output is correct |
19 |
Correct |
327 ms |
23284 KB |
Output is correct |
20 |
Correct |
1382 ms |
41136 KB |
Output is correct |
21 |
Correct |
769 ms |
29992 KB |
Output is correct |
22 |
Correct |
500 ms |
25728 KB |
Output is correct |
23 |
Correct |
1379 ms |
41092 KB |
Output is correct |
24 |
Correct |
1404 ms |
41240 KB |
Output is correct |
25 |
Correct |
1374 ms |
41208 KB |
Output is correct |
26 |
Correct |
335 ms |
23256 KB |
Output is correct |
27 |
Correct |
310 ms |
22828 KB |
Output is correct |
28 |
Correct |
316 ms |
22952 KB |
Output is correct |
29 |
Correct |
325 ms |
23312 KB |
Output is correct |
30 |
Correct |
305 ms |
23196 KB |
Output is correct |
31 |
Correct |
5 ms |
3192 KB |
Output is correct |
32 |
Correct |
4 ms |
3192 KB |
Output is correct |
33 |
Correct |
5 ms |
3192 KB |
Output is correct |
34 |
Correct |
5 ms |
3320 KB |
Output is correct |
35 |
Correct |
5 ms |
3148 KB |
Output is correct |
36 |
Correct |
5 ms |
3192 KB |
Output is correct |
37 |
Correct |
4 ms |
3192 KB |
Output is correct |
38 |
Correct |
5 ms |
3192 KB |
Output is correct |
39 |
Correct |
5 ms |
3192 KB |
Output is correct |
40 |
Correct |
4 ms |
3192 KB |
Output is correct |
41 |
Correct |
608 ms |
16972 KB |
Output is correct |
42 |
Correct |
1119 ms |
29508 KB |
Output is correct |
43 |
Correct |
1138 ms |
29384 KB |
Output is correct |
44 |
Correct |
324 ms |
12012 KB |
Output is correct |
45 |
Correct |
1132 ms |
29296 KB |
Output is correct |
46 |
Correct |
1125 ms |
29408 KB |
Output is correct |
47 |
Correct |
1125 ms |
29212 KB |
Output is correct |
48 |
Correct |
1166 ms |
29348 KB |
Output is correct |
49 |
Correct |
1167 ms |
29380 KB |
Output is correct |
50 |
Correct |
1137 ms |
29216 KB |
Output is correct |
51 |
Correct |
1128 ms |
29356 KB |
Output is correct |
52 |
Correct |
1128 ms |
29476 KB |
Output is correct |
53 |
Correct |
1117 ms |
29360 KB |
Output is correct |
54 |
Correct |
1100 ms |
29420 KB |
Output is correct |
55 |
Correct |
1111 ms |
29664 KB |
Output is correct |
56 |
Correct |
1136 ms |
29520 KB |
Output is correct |
57 |
Correct |
1120 ms |
29500 KB |
Output is correct |
58 |
Correct |
1144 ms |
29472 KB |
Output is correct |
59 |
Correct |
267 ms |
12008 KB |
Output is correct |
60 |
Correct |
1215 ms |
29448 KB |
Output is correct |
61 |
Correct |
895 ms |
30508 KB |
Output is correct |
62 |
Correct |
215 ms |
13420 KB |
Output is correct |
63 |
Correct |
253 ms |
12648 KB |
Output is correct |
64 |
Correct |
217 ms |
13292 KB |
Output is correct |
65 |
Correct |
223 ms |
13388 KB |
Output is correct |
66 |
Correct |
309 ms |
12620 KB |
Output is correct |
67 |
Correct |
312 ms |
12012 KB |
Output is correct |
68 |
Correct |
230 ms |
13292 KB |
Output is correct |
69 |
Correct |
315 ms |
12084 KB |
Output is correct |
70 |
Correct |
222 ms |
13420 KB |
Output is correct |
71 |
Correct |
272 ms |
12012 KB |
Output is correct |
72 |
Correct |
870 ms |
29524 KB |
Output is correct |
73 |
Correct |
1344 ms |
41300 KB |
Output is correct |
74 |
Correct |
1351 ms |
41100 KB |
Output is correct |
75 |
Correct |
1342 ms |
41296 KB |
Output is correct |
76 |
Correct |
1307 ms |
41096 KB |
Output is correct |
77 |
Correct |
1291 ms |
40984 KB |
Output is correct |
78 |
Correct |
1310 ms |
41264 KB |
Output is correct |
79 |
Correct |
1295 ms |
41244 KB |
Output is correct |
80 |
Correct |
1319 ms |
41196 KB |
Output is correct |
81 |
Correct |
1313 ms |
41104 KB |
Output is correct |
82 |
Correct |
1317 ms |
41320 KB |
Output is correct |
83 |
Correct |
1307 ms |
41268 KB |
Output is correct |
84 |
Correct |
1322 ms |
40992 KB |
Output is correct |
85 |
Correct |
1319 ms |
41208 KB |
Output is correct |
86 |
Correct |
1305 ms |
41076 KB |
Output is correct |
87 |
Correct |
1301 ms |
41240 KB |
Output is correct |
88 |
Correct |
1297 ms |
41252 KB |
Output is correct |
89 |
Correct |
503 ms |
25760 KB |
Output is correct |
90 |
Correct |
1284 ms |
41252 KB |
Output is correct |
91 |
Correct |
1076 ms |
41924 KB |
Output is correct |
92 |
Correct |
286 ms |
23316 KB |
Output is correct |
93 |
Correct |
427 ms |
24580 KB |
Output is correct |
94 |
Correct |
311 ms |
23108 KB |
Output is correct |
95 |
Correct |
303 ms |
23384 KB |
Output is correct |
96 |
Correct |
458 ms |
22616 KB |
Output is correct |
97 |
Correct |
464 ms |
24684 KB |
Output is correct |
98 |
Correct |
311 ms |
23112 KB |
Output is correct |
99 |
Correct |
466 ms |
24424 KB |
Output is correct |
100 |
Correct |
352 ms |
22968 KB |
Output is correct |