이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef pair<int , int> ipair;
const int N = 5e5 + 5;
struct TEdges{
int u , v , w;
bool operator<(const TEdges &X) const{
return w > X.w;
}
};
int n , m , k , q;
vector<ipair> adj[N];
TEdges E[N];
priority_queue<ipair , vector<ipair> , greater<ipair>> pq;
int d[N] , P[N][20] , depth[N] , mn[N][20] , sz[N] , p[N];
int Find(int x){
return (x == p[x]) ? x : p[x] = Find(p[x]);
}
int Union(int u , int v){
int U = Find(u) ,V = Find(v);
if(U == V) return 0;
if(sz[U] < sz[V]) swap(U , V);
sz[U] += sz[V]; p[V] = U;
return 1;
}
void dfs(int u, int p ){
P[u][0]= p;
for(int i = 1; i <= 17; ++i) {P[u][i] = P[P[u][u - 1]][i - 1] ; mn[u][i] = min(mn[u][i - 1] , mn[P[u][i - 1]][i - 1]); }
for(auto X : adj[u]){
int v = X.f , w = X.s;
if(v == p) continue;
mn[v][0] = w;
depth[v] = depth[u] + 1;
dfs(v ,u);
}
}
int LCA(int u, int v){
int res = 2e9;
if(depth[u] < depth[v]) swap(u , v);
int k = depth[u] - depth[v];
for(int i = 17; ~i; --i){
if(k>>i&1){ res = min(res , mn[u][i]) ; u= P[u][i];
}
}
if(u == v) return res;
for(int i = 17; ~i; --i){
if(P[u][i] != P[v][i]){
res = min({res , mn[u][i] , mn[v][i]}); u = P[u][i] ; v = P[v][i];
}
}
return min({res , mn[u][0] , mn[v][0]});
}
int main (){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for(int i = 0; i < m; ++i){
int u , v , w; cin >> u >> v >> w;--u;--v;
adj[u].emplace_back(v , w); adj[v].emplace_back(u , w);
E[i].u = u; E[i].v = v; E[i].w = w;
}
cin >> k;
for(int i = 0; i < n; ++i) d[i] = 2e9;
for(int i= 0;i < k; ++i){
int u; cin >> u;--u;
d[u] = 0; pq.push({0 , u});
}
while(!pq.empty()){
auto X = pq.top(); pq.pop();
if(X.f != d[X.s]) continue;
for(ipair N : adj[X.s]){
if(d[N.f] > X.f + N.s){
d[N.f] = X.f + N.s;
pq.push({d[N.f], N.f});
}
}
}
for(int i = 0; i < n; ++i) for(int j = 0; j < 20; ++j) mn[i][j] = 2e9;
for(int i = 0; i < n; ++i) p[i] = i , sz[i] = 1;
for(int i = 0; i < m; ++i) E[i].w = min(d[E[i].u] , d[E[i].v]);
for(int i = 0; i < n; ++i) adj[i].clear();
sort(E , E + m);
for(int i = 0; i < m; ++i){
int u = E[i].u , v = E[i].v ,w = E[i].w;
if(Union(u , v)){
adj[u].emplace_back(v , w); adj[v].emplace_back(u , w);
}
}
dfs(0 ,-1);
cin >> q;
while(q--){
int u , v;
cin >> u >> v;--u;--v;
cout << LCA(u ,v) << endl;
}
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... |