이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using i64 = long long;
#define int i64
constexpr int Inf = 1E14 + 5;
constexpr int N = 1E5 + 5;
constexpr int L = 3;
int par[N][L];
int dis[N][L];
void solve() {
int n, s, q, e;
std::cin >> n >> s >> q >> e;
std::vector<std::array<int, 3>> edges(n - 1);
std::vector<std::pair<int, int>> adj[n + 1];
for(int i = 0; i < n - 1; i++) {
std::cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
adj[--edges[i][0]].emplace_back(--edges[i][1], edges[i][2]);
adj[edges[i][1]].emplace_back(edges[i][0], edges[i][2]);
}
std::vector<int> shops(n);
for(int i = 0; i < s; i++) {
int x;
std::cin >> x;
x--;
shops[x] = true;
}
int timer = 0;
std::vector<int> tin(n), tout(n), dist(n), depth(n);
std::function<void(int)> dfs = [&](int node) -> void {
tin[node] = ++timer;
for(auto [child, d] : adj[node]) {
if(tin[child] == 0) {
par[child][0] = node;
depth[child] = depth[node] + 1;
dist[child] = dist[node] + d;
dfs(child);
}
}
tout[node] = ++timer;
return;
};
par[e][0] = e;
dfs(--e);
for(int i = 0; i < n - 1; i++) {
auto &[u, v, d] = edges[i];
if(depth[u] > depth[v]) {
std::swap(u, v);
}
}
std::vector<int> magic(n, -1);
dfs = [&](int node) -> void {
magic[node] = Inf;
for(auto [child, d] : adj[node]) {
if(magic[child] == -1) {
dfs(child);
magic[node] = std::min(magic[node], magic[child]);
}
}
if(shops[node]) {
magic[node] = std::min(magic[node], dist[node]);
} else {
magic[node] = std::min(magic[node], Inf);
}
return;
};
dfs(e);
for(int node = 0; node < n; node++) {
if(magic[node] != Inf) {
magic[node] -= 2 * dist[node];
}
//std::cerr << magic[node] << " \n"[node == n - 1];
dis[node][0] = magic[par[node][0]];
}
for(int lg = 1; lg < L; lg++) {
for(int i = 0; i < n; i++) {
par[i][lg] = par[par[i][lg - 1]][lg - 1];
dis[i][lg] = std::min(dis[i][lg - 1], dis[par[i][lg - 1]][lg - 1]);
//std::cerr << i << " " << lg << " || " << dis[i][lg - 1] << " " << dis[par[i][lg - 1]][lg - 1] << "\n";
}
}
for(int cCc = 1; cCc <= q; cCc++) {
int I, R;
std::cin >> I >> R;
I--; R--;
int node = edges[I][1];
//std::cerr << "query: " << cCc << " ? " << I << " " << R << " :: " << node << " -> " << tin[node] << " " << tin[R] << " " << tout[R] << " " << tout[node] << "\n";
if(tin[node] <= tin[R] && tout[R] <= tout[node]) {
int ans = Inf, bef = R;
for(int lg = L - 1; lg >= 0; lg--) {
int nxt = par[R][lg];
if(tin[node] <= tin[nxt] && tout[nxt] <= tout[node]) {
//std::cerr << "zipla: " << R << " " << lg << " -> " << nxt << " :: " << dis[R][lg] << "\n";
ans = std::min(ans, dis[R][lg]);
R = nxt;
}
}
if(ans != Inf) {
std::cout << ans + dist[bef] << "\n";
} else {
std::cout << "oo\n";
}
} else {
std::cout << "escaped\n";
}
}
return;
}
signed main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL); std::cout.tie(NULL);
int t = 1; //std::cin >> t;
for(int i = 1; i <= t; i++) {
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... |