This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define msi multiset<int>
#define si set<int>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
const int mod = 1e9 + 7;
const int MOD = 998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 30;
const int MAXN = 1e6 + 2;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
struct uf{
int par[MAXN], sz[MAXN];
void init(int n){
for(int i=1; i<=n; i++) par[i] = i, sz[i] = 1;
}
int find(int x){
return par[x] == x ? x : par[x] = find(par[x]);
}
void unite(int a, int b){
a = find(a), b = find(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a;
sz[a] += sz[b];
}
bool query(int a, int b){
return find(a) == find(b);
}
}uf;
int lo[MAXN], hi[MAXN], dis[MAXN], cj, n, m, q, st[MAXN], en[MAXN], ans[MAXN];
vii g[MAXN];
vector<pair<int, ii>> brid;
vi qs;
bool cmp(int a, int b){
return lo[a] > lo[b];
}
void paralelni(){
sort(all(qs), cmp);
cj = 0;
uf.init(n);
for(auto &x : qs){
if(lo[x] > hi[x]) continue;
int mid = (lo[x] + hi[x]) / 2;
while(cj < (int)brid.size() and brid[cj].X >= mid) uf.unite(brid[cj].Y.X, brid[cj].Y.Y), cj++;
if(uf.query(st[x], en[x])) lo[x] = mid + 1, ans[x] = mid;
else hi[x] = mid - 1;
}
}
void dijkstra(){
set<ii> s;
for(int i=1; i<=n; i++) s.insert({dis[i], i});
while(!s.empty()){
ii cur = *s.begin();
s.erase(s.begin());
int u = cur.Y, d = cur.X;
for(auto &x : g[u]){
int nd = d + x.Y;
if(nd < dis[x.X]){
s.erase({dis[x.X], x.X});
dis[x.X] = nd;
s.insert({dis[x.X], x.X});
}
}
}
for(int i=1; i<=n; i++){
for(auto &x : g[i]) if(dis[i] < dis[x.X]) brid.PB({dis[i], {i, x.X}});
}
sort(all(brid));
reverse(all(brid));
}
void solve(){
cin >> n >> m;
for(int i=1; i<=m; i++){
int a, b, w;
cin >> a >> b >> w;
g[a].PB({b, w});
g[b].PB({a, w});
}
int k;
cin >> k;
for(int i=1; i<=n; i++) dis[i] = inf;
for(int i=1, x; i<=k; i++) cin >> x, dis[x] = 0;
dijkstra();
cin >> q;
for(int i=0; i<q; i++){
cin >> st[i] >> en[i];
lo[i] = 0, hi[i] = inf, ans[i] = inf;
qs.PB(i);
}
for(int i=0; i<32; i++) paralelni();
for(int i=0; i<q; i++) cout << ans[i] << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |