이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
using namespace std;
const int N = 2 * 1e5 + 5;
const int MOD = 1e9 + 7;
const int K = 18;
const long long inf = 1e18;
int n, m, h[N], q, a[N], b[N], t[N], r[N], parent[N], par[N][K], s, e, x[N], son;
vector<pair<int, int>> g[N];
long long d[N];
void dfs(int v, int pr){
par[v][0] = pr;
for(auto to : g[v]){
if(to.F != pr){
d[to.F] = d[v] + to.S;
h[to.F] = h[v] + 1;
dfs(to.F, v);
}
}
}
bool bit(int x, int p){
return x & (1 << p);
}
int lift(int v, int k){
for(int i = 0; i < K; i++){
if (bit(k, i)) {
v = par[v][i];
}
}
return v;
}
int lca(int a, int b){
if(h[a] < h[b]){
swap(a, b);
}
a = lift(a, h[a] - h[b]);
if(a == b){
return a;
}
for(int i = K - 1; i >= 0; --i){
if(par[a][i] != par[b][i]){
a = par[a][i];
b = par[b][i];
}
}
return par[a][0];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> s >> q >> e;
for(int i = 1, u, v, w; i < n; i++){
cin >> u >> v >> w;
g[u].pb({v, w});
g[v].pb({u, w});
a[i] = u;
b[i] = v;
}
dfs(1, 1);
for(int i = 1; i < K; i++){
for(int v = 1; v <= n; v++){
par[v][i] = par[par[v][i - 1]][i - 1];
}
}
for(int i = 1; i <= s; ++i){
cin >> x[i];
}
for(int i = 1; i <= q; ++i){
cin >> t[i] >> r[i];
if(par[a[t[i]]][0] == b[t[i]]) son = a[t[i]];
else son = b[t[i]];
if(lca(son, r[i]) == son){
if(lca(son, e) == son) {cout << "escaped\n"; continue;}
else {
ll res = inf;
if(s == n){
res = 0;
}
else
for(int j = 1; j <= s; ++j){
if(lca(x[j], son) == son){
res = min(res, d[x[j]] + d[r[i]] - d[lca(r[i], x[j])] * 2);
}
}
if(res == inf) cout << "oo\n";
else cout << res << '\n';
}
}
else{
if(lca(son, e) != son) {cout << "escaped\n"; continue;}
else{
ll res = inf;
if(s == n){
res = 0;
}
else
for(int j = 1; j <= s; ++j){
if(lca(x[j], son) != son){
res = min(res, d[x[j]] + d[r[i]] - d[lca(r[i], x[j])] * 2);
}
}
if(res == inf) cout << "oo\n";
else cout << res << '\n';
}
}
}
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... |