이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/* IN THE NAME OF GOD */
/* |\/| /-\ |\| | |\/| /-\ */
#include "bits/stdc++.h"
using namespace std;
#define sz(x) (int)x.size()
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define mr make_pair
//#define int long long
#define pii pair<int, int>
typedef long double ld;
typedef long long ll;
mt19937 rng (chrono::high_resolution_clock::now().time_since_epoch().count());
const int N = 1e5 + 10;
const int MOD = 1e9 + 7;
const int inf = 1e9 + 1;
const ll INF = 3e18;
vector<pii> g[N];
int tin[N], tout[N], T, par[N][20], h[N];
ll b[N][20], d[N], f[N];
bool shop[N];
void pdfs(int v, int p){
tin[v] = ++T;
if(shop[v])
f[v] = 0;
for(int i = 1; i < 20; i++)
par[v][i] = par[par[v][i - 1]][i - 1];
for(pii u : g[v]){
if(u.F == p)
continue;
par[u.F][0] = v;
d[u.F] = d[v] + u.S;
h[u.F] = h[v] + 1;
pdfs(u.F, v);
f[v] = min(f[v], f[u.F] + u.S);
}
tout[v] = ++T;
}
void dfs(int v, int p){
for(int i = 1; i < 20; i++)
b[v][i] = min(b[v][i - 1], b[par[v][i - 1]][i - 1] + d[v] - d[par[v][i - 1]]);
for(pii u : g[v]){
if(u.F == p)
continue;
b[u.F][0] = f[v] + u.S;
b[u.F][0] = min(b[u.F][0], f[u.F]);
if(u.F == 5)
cout << b[u.F][0] << endl;
dfs(u.F, v);
}
}
int32_t main(){
ios_base:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, s, q, end;
cin >> n >> s >> q >> end;
int u, v, w;
vector<pii> e;
for(int i = 1; i < n; i++){
cin >> u >> v >> w;
g[u].pb(mr(v, w));
g[v].pb(mr(u, w));
e.pb(mr(u, v));
}
for(int i = 1; i <= s; i++){
cin >> v;
shop[v] = 1;
}
for(int i = 1; i <= n; i++)
f[i] = INF;
pdfs(end, 0);
dfs(end, 0);
while(q--){
cin >> w >> v;
w--;
if(tin[e[w].F] < tin[e[w].S])
swap(e[w].F, e[w].S);
bool f1 = (tin[e[w].F] <= tin[v] && tout[e[w].F] >= tout[v]), f2 = (tin[e[w].F] <= tin[end] && tout[e[w].F] >= tout[end]);
if(!(f1 ^ f2))
cout << "escaped" << endl;
else{
if(f1){
int H = h[v] - h[e[w].F];
ll ans = f[v], D = 0;
for(int j = 0; j < 20; j++){
if(H & (1 << j)){
ans = min(ans, b[v][j] + D);
D += d[v] - d[par[v][j]];
v = par[v][j];
}
}
if(ans == INF)
cout << "oo" << endl;
else
cout << ans << endl;
}
}
}
}
# | 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... |