#include <bits/stdc++.h>
#include <random>
#define int long long
#define fi first
#define se second
#define pb push_back
#define md ((l+r)>>1)
#define lf (id<<1)
#define rg ((id<<1)|1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 2e5+10;
const int MAXA = 1e6+10;
const int INF = 2e9+10;
const int LOG = 30;
const int MOD = 1e9+7;
int n, m, K, Q;
vector <pii> adj[MAXN];
vector <int> vec;
int dis[MAXN], val[MAXN];
priority_queue <pii, vector<pii>, greater<pii>> pq;
void dji(){
for(int i=1; i<=n; i++) val[i] = INF;
for(auto in : vec){
val[in] = 0;
pq.push({0, in});
}
while(!pq.empty()){
int nw = pq.top().se, dist = pq.top().fi;
pq.pop();
// cout << nw << " dist\n";
if(val[nw] < dist) continue;
for(auto ed : adj[nw]){
int nx = ed.fi, wei = ed.se;
if(val[nx] > val[nw]+wei){
val[nx] = val[nw]+wei;
pq.push({val[nx],nx});
}
}
}
}
struct dsu {
int par[MAXN];
void bd(){
for(int i=1; i<=n; i++) par[i] = i;
}
int f(int x){
if(par[x] == x) return x;
return par[x] = f(par[x]);
}
bool con(int x, int y){
return f(x) == f(y);
}
void mer(int x, int y){
x = f(x); y = f(y);
if(con(x, y)) return;
par[x] = y;
}
} DSU;
int ans[MAXN], x[MAXN], y[MAXN];
vector <ipii> solve[MAXN];
vector <pii> seg;
signed main() {
// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i=1; i<=m; i++){
int x, y, w; cin >> x >> y >> w;
adj[x].pb({y, w}); adj[y].pb({x, w});
}
cin >> K;
for(int i=1; i<=K; i++){
int p; cin >> p;
vec.pb(p);
}
dji();
// for(int i=1; i<=n; i++) cout << val[i] << " \n"[i==n];
for(int i=1; i<=n; i++) seg.pb({val[i], i});
sort(seg.rbegin(), seg.rend());
// for(auto in : seg) cout << in.fi << " ";
// cout << " xx\n";
cin >> Q;
for(int i=1; i<=Q; i++){
cin >> x[i] >> y[i]; // l = 1, r = val[x]
int l = 1, r = val[x[i]];
int ll = 0, rr = seg.size()-1, mid=0, cnt=-1;
while(ll<=rr){
mid = (ll+rr)/2;
if(seg[mid].fi <= val[x[i]]){
cnt = mid; rr = mid-1;
} else ll = mid+1;
}
if(cnt==-1) continue;
while(cnt+1 < seg.size() && seg[cnt+1].fi==seg[cnt].fi) cnt++;
solve[cnt/2].pb({i, {cnt, seg.size()-1}});
// cout << i << ' '<< cnt << ' ' << val[x[i]] << " cnt\n";
}
bool done = 0;
while(!done){
done = 1;
DSU.bd();
for(int i=0; i<seg.size(); i++){
for(auto ed : adj[seg[i].se]){
int nx = ed.fi;
if(val[nx] >= seg[i].fi){
DSU.mer(seg[i].se, nx);
// cout << seg[i].se << ' '<< nx << " nx\n";
}
}
vector <ipii> upd;
for(auto in : solve[i]){
int idx = in.fi, l = in.se.fi, r = in.se.se;
int nl = l, nr = r;
if(DSU.con(x[idx], y[idx])){
ans[idx] = seg[i].fi;
nr = i-1;
if(nl > nr) continue;
// cout << nl << ' ' << nr << " nlr\n";
done = 0;
upd.pb({idx, {nl, nr}});
} else {
nl = i+1;
if(nl > nr) continue;
done = 0;
upd.pb({idx, {nl, nr}});
}
}
solve[i].clear();
for(auto in : upd) solve[(in.se.fi+in.se.se)/2].pb(in);
}
}
for(int i=1; i<=Q; i++) cout << ans[i] << "\n";
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:101:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | while(cnt+1 < seg.size() && seg[cnt+1].fi==seg[cnt].fi) cnt++;
| ~~~~~~^~~~~~~~~~~~
plan.cpp:91:7: warning: unused variable 'l' [-Wunused-variable]
91 | int l = 1, r = val[x[i]];
| ^
plan.cpp:91:14: warning: unused variable 'r' [-Wunused-variable]
91 | int l = 1, r = val[x[i]];
| ^
plan.cpp:110:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int i=0; i<seg.size(); i++){
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
19444 KB |
Output is correct |
2 |
Correct |
6 ms |
19488 KB |
Output is correct |
3 |
Correct |
6 ms |
19548 KB |
Output is correct |
4 |
Correct |
3 ms |
19036 KB |
Output is correct |
5 |
Correct |
5 ms |
19548 KB |
Output is correct |
6 |
Correct |
5 ms |
19392 KB |
Output is correct |
7 |
Correct |
3 ms |
19036 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
6 ms |
19292 KB |
Output is correct |
10 |
Correct |
6 ms |
19548 KB |
Output is correct |
11 |
Correct |
6 ms |
19292 KB |
Output is correct |
12 |
Correct |
6 ms |
19548 KB |
Output is correct |
13 |
Correct |
5 ms |
19544 KB |
Output is correct |
14 |
Correct |
6 ms |
19380 KB |
Output is correct |
15 |
Correct |
6 ms |
19388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
19444 KB |
Output is correct |
2 |
Correct |
6 ms |
19488 KB |
Output is correct |
3 |
Correct |
6 ms |
19548 KB |
Output is correct |
4 |
Correct |
3 ms |
19036 KB |
Output is correct |
5 |
Correct |
5 ms |
19548 KB |
Output is correct |
6 |
Correct |
5 ms |
19392 KB |
Output is correct |
7 |
Correct |
3 ms |
19036 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
6 ms |
19292 KB |
Output is correct |
10 |
Correct |
6 ms |
19548 KB |
Output is correct |
11 |
Correct |
6 ms |
19292 KB |
Output is correct |
12 |
Correct |
6 ms |
19548 KB |
Output is correct |
13 |
Correct |
5 ms |
19544 KB |
Output is correct |
14 |
Correct |
6 ms |
19380 KB |
Output is correct |
15 |
Correct |
6 ms |
19388 KB |
Output is correct |
16 |
Correct |
449 ms |
61924 KB |
Output is correct |
17 |
Correct |
1185 ms |
96164 KB |
Output is correct |
18 |
Correct |
64 ms |
24904 KB |
Output is correct |
19 |
Correct |
227 ms |
82220 KB |
Output is correct |
20 |
Correct |
1237 ms |
96484 KB |
Output is correct |
21 |
Correct |
1855 ms |
78796 KB |
Output is correct |
22 |
Correct |
340 ms |
49348 KB |
Output is correct |
23 |
Correct |
1205 ms |
96132 KB |
Output is correct |
24 |
Correct |
1176 ms |
96108 KB |
Output is correct |
25 |
Correct |
1346 ms |
96632 KB |
Output is correct |
26 |
Correct |
274 ms |
74064 KB |
Output is correct |
27 |
Correct |
235 ms |
79348 KB |
Output is correct |
28 |
Correct |
256 ms |
75112 KB |
Output is correct |
29 |
Correct |
239 ms |
80740 KB |
Output is correct |
30 |
Correct |
234 ms |
86784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
19032 KB |
Output is correct |
2 |
Correct |
3 ms |
19036 KB |
Output is correct |
3 |
Correct |
4 ms |
19032 KB |
Output is correct |
4 |
Correct |
3 ms |
19036 KB |
Output is correct |
5 |
Correct |
4 ms |
19036 KB |
Output is correct |
6 |
Correct |
4 ms |
19036 KB |
Output is correct |
7 |
Correct |
4 ms |
19036 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
4 ms |
19220 KB |
Output is correct |
10 |
Correct |
4 ms |
19036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
370 ms |
32500 KB |
Output is correct |
2 |
Correct |
775 ms |
57212 KB |
Output is correct |
3 |
Correct |
773 ms |
57152 KB |
Output is correct |
4 |
Correct |
86 ms |
27072 KB |
Output is correct |
5 |
Correct |
602 ms |
56940 KB |
Output is correct |
6 |
Correct |
680 ms |
57096 KB |
Output is correct |
7 |
Correct |
787 ms |
57160 KB |
Output is correct |
8 |
Correct |
699 ms |
56824 KB |
Output is correct |
9 |
Correct |
675 ms |
57208 KB |
Output is correct |
10 |
Correct |
647 ms |
57060 KB |
Output is correct |
11 |
Correct |
710 ms |
57148 KB |
Output is correct |
12 |
Correct |
691 ms |
57152 KB |
Output is correct |
13 |
Correct |
777 ms |
57164 KB |
Output is correct |
14 |
Correct |
733 ms |
56956 KB |
Output is correct |
15 |
Correct |
705 ms |
60084 KB |
Output is correct |
16 |
Correct |
695 ms |
57108 KB |
Output is correct |
17 |
Correct |
750 ms |
57068 KB |
Output is correct |
18 |
Correct |
740 ms |
57132 KB |
Output is correct |
19 |
Correct |
144 ms |
27080 KB |
Output is correct |
20 |
Correct |
773 ms |
57204 KB |
Output is correct |
21 |
Correct |
884 ms |
57552 KB |
Output is correct |
22 |
Correct |
136 ms |
30028 KB |
Output is correct |
23 |
Correct |
130 ms |
27588 KB |
Output is correct |
24 |
Correct |
112 ms |
29352 KB |
Output is correct |
25 |
Correct |
131 ms |
29896 KB |
Output is correct |
26 |
Correct |
108 ms |
27568 KB |
Output is correct |
27 |
Correct |
86 ms |
27224 KB |
Output is correct |
28 |
Correct |
124 ms |
29404 KB |
Output is correct |
29 |
Correct |
88 ms |
27080 KB |
Output is correct |
30 |
Correct |
108 ms |
29368 KB |
Output is correct |
31 |
Correct |
108 ms |
27012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
19444 KB |
Output is correct |
2 |
Correct |
6 ms |
19488 KB |
Output is correct |
3 |
Correct |
6 ms |
19548 KB |
Output is correct |
4 |
Correct |
3 ms |
19036 KB |
Output is correct |
5 |
Correct |
5 ms |
19548 KB |
Output is correct |
6 |
Correct |
5 ms |
19392 KB |
Output is correct |
7 |
Correct |
3 ms |
19036 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
6 ms |
19292 KB |
Output is correct |
10 |
Correct |
6 ms |
19548 KB |
Output is correct |
11 |
Correct |
6 ms |
19292 KB |
Output is correct |
12 |
Correct |
6 ms |
19548 KB |
Output is correct |
13 |
Correct |
5 ms |
19544 KB |
Output is correct |
14 |
Correct |
6 ms |
19380 KB |
Output is correct |
15 |
Correct |
6 ms |
19388 KB |
Output is correct |
16 |
Correct |
449 ms |
61924 KB |
Output is correct |
17 |
Correct |
1185 ms |
96164 KB |
Output is correct |
18 |
Correct |
64 ms |
24904 KB |
Output is correct |
19 |
Correct |
227 ms |
82220 KB |
Output is correct |
20 |
Correct |
1237 ms |
96484 KB |
Output is correct |
21 |
Correct |
1855 ms |
78796 KB |
Output is correct |
22 |
Correct |
340 ms |
49348 KB |
Output is correct |
23 |
Correct |
1205 ms |
96132 KB |
Output is correct |
24 |
Correct |
1176 ms |
96108 KB |
Output is correct |
25 |
Correct |
1346 ms |
96632 KB |
Output is correct |
26 |
Correct |
274 ms |
74064 KB |
Output is correct |
27 |
Correct |
235 ms |
79348 KB |
Output is correct |
28 |
Correct |
256 ms |
75112 KB |
Output is correct |
29 |
Correct |
239 ms |
80740 KB |
Output is correct |
30 |
Correct |
234 ms |
86784 KB |
Output is correct |
31 |
Correct |
5 ms |
19032 KB |
Output is correct |
32 |
Correct |
3 ms |
19036 KB |
Output is correct |
33 |
Correct |
4 ms |
19032 KB |
Output is correct |
34 |
Correct |
3 ms |
19036 KB |
Output is correct |
35 |
Correct |
4 ms |
19036 KB |
Output is correct |
36 |
Correct |
4 ms |
19036 KB |
Output is correct |
37 |
Correct |
4 ms |
19036 KB |
Output is correct |
38 |
Correct |
4 ms |
19036 KB |
Output is correct |
39 |
Correct |
4 ms |
19220 KB |
Output is correct |
40 |
Correct |
4 ms |
19036 KB |
Output is correct |
41 |
Correct |
370 ms |
32500 KB |
Output is correct |
42 |
Correct |
775 ms |
57212 KB |
Output is correct |
43 |
Correct |
773 ms |
57152 KB |
Output is correct |
44 |
Correct |
86 ms |
27072 KB |
Output is correct |
45 |
Correct |
602 ms |
56940 KB |
Output is correct |
46 |
Correct |
680 ms |
57096 KB |
Output is correct |
47 |
Correct |
787 ms |
57160 KB |
Output is correct |
48 |
Correct |
699 ms |
56824 KB |
Output is correct |
49 |
Correct |
675 ms |
57208 KB |
Output is correct |
50 |
Correct |
647 ms |
57060 KB |
Output is correct |
51 |
Correct |
710 ms |
57148 KB |
Output is correct |
52 |
Correct |
691 ms |
57152 KB |
Output is correct |
53 |
Correct |
777 ms |
57164 KB |
Output is correct |
54 |
Correct |
733 ms |
56956 KB |
Output is correct |
55 |
Correct |
705 ms |
60084 KB |
Output is correct |
56 |
Correct |
695 ms |
57108 KB |
Output is correct |
57 |
Correct |
750 ms |
57068 KB |
Output is correct |
58 |
Correct |
740 ms |
57132 KB |
Output is correct |
59 |
Correct |
144 ms |
27080 KB |
Output is correct |
60 |
Correct |
773 ms |
57204 KB |
Output is correct |
61 |
Correct |
884 ms |
57552 KB |
Output is correct |
62 |
Correct |
136 ms |
30028 KB |
Output is correct |
63 |
Correct |
130 ms |
27588 KB |
Output is correct |
64 |
Correct |
112 ms |
29352 KB |
Output is correct |
65 |
Correct |
131 ms |
29896 KB |
Output is correct |
66 |
Correct |
108 ms |
27568 KB |
Output is correct |
67 |
Correct |
86 ms |
27224 KB |
Output is correct |
68 |
Correct |
124 ms |
29404 KB |
Output is correct |
69 |
Correct |
88 ms |
27080 KB |
Output is correct |
70 |
Correct |
108 ms |
29368 KB |
Output is correct |
71 |
Correct |
108 ms |
27012 KB |
Output is correct |
72 |
Correct |
786 ms |
70008 KB |
Output is correct |
73 |
Correct |
1254 ms |
95644 KB |
Output is correct |
74 |
Correct |
1224 ms |
95704 KB |
Output is correct |
75 |
Correct |
1201 ms |
95864 KB |
Output is correct |
76 |
Correct |
1254 ms |
95496 KB |
Output is correct |
77 |
Correct |
1239 ms |
95780 KB |
Output is correct |
78 |
Correct |
1146 ms |
96064 KB |
Output is correct |
79 |
Correct |
1182 ms |
95580 KB |
Output is correct |
80 |
Correct |
1129 ms |
95632 KB |
Output is correct |
81 |
Correct |
1150 ms |
95212 KB |
Output is correct |
82 |
Correct |
1219 ms |
95640 KB |
Output is correct |
83 |
Correct |
1262 ms |
95380 KB |
Output is correct |
84 |
Correct |
1214 ms |
95612 KB |
Output is correct |
85 |
Correct |
1431 ms |
97676 KB |
Output is correct |
86 |
Correct |
1223 ms |
95452 KB |
Output is correct |
87 |
Correct |
1254 ms |
95504 KB |
Output is correct |
88 |
Correct |
1120 ms |
95336 KB |
Output is correct |
89 |
Correct |
345 ms |
49552 KB |
Output is correct |
90 |
Correct |
1169 ms |
95592 KB |
Output is correct |
91 |
Correct |
3844 ms |
70400 KB |
Output is correct |
92 |
Correct |
241 ms |
79480 KB |
Output is correct |
93 |
Correct |
401 ms |
54768 KB |
Output is correct |
94 |
Correct |
282 ms |
69252 KB |
Output is correct |
95 |
Correct |
274 ms |
78016 KB |
Output is correct |
96 |
Correct |
393 ms |
70720 KB |
Output is correct |
97 |
Correct |
348 ms |
64220 KB |
Output is correct |
98 |
Correct |
272 ms |
67872 KB |
Output is correct |
99 |
Correct |
342 ms |
64192 KB |
Output is correct |
100 |
Correct |
266 ms |
74936 KB |
Output is correct |