| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 790132 | tch1cherin | Valley (BOI19_valley) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int L = __lg(N) + 2;
vector<tuple<int, int, int>> g[N];
int dp[L][N], ancestors[N][L], depth[N], edges[N][3], sz[N], cnt[N];
long long weight[L][N], dp_down[N], dp_up[N], dp_val[N], dist[N];
bool used[N], has_shop[N];
unordered_map<int, long long> min_excluding[N];
void build_lifting(int u = 0, int p = 0) {
dp[0][u] = p;
depth[u] = p == 0 ? 0 : depth[p] + 1;
for (int i = 1; i < L; i++) {
dp[i][u] = dp[i - 1][dp[i - 1][u]];
weight[i][u] = weight[i - 1][u] + weight[i - 1][dp[i - 1][u]];
}
for (auto [i, v, w] : g[u]) {
if (v != p) {
weight[0][v] = w;
build_lifting(v, u);
}
}
}
long long dis(int u, int v) {
if (depth[u] < depth[v]) {
swap(u, v);
}
long long ans = 0;
for (int i = L - 1; i >= 0; i--) {
if (depth[u] - (1 << i) >= depth[v]) {
ans += weight[i][u];
u = dp[i][u];
}
}
if (u == v) {
return ans;
}
for (int i = L - 1; i >= 0; i--) {
if (dp[i][u] != dp[i][v]) {
ans += weight[i][u] + weight[i][v];
u = dp[i][u], v = dp[i][v];
}
}
ans += weight[0][u] + weight[0][v];
return ans;
}
bool check(int a, int b, int i) {
return min(dis(a, edges[i][0]) + dis(edges[i][1], b), dis(b, edges[i][0]) + dis(a, edges[i][1])) + edges[i][2] == dis(a, b);
}
void sizes(int u, int p) {
sz[u] = 1;
for (auto [i, v, w] : g[u]) {
if (v != p && !used[v]) {
sizes(v, u);
sz[u] += sz[v];
}
}
}
int centroid(int u, int p, int n) {
for (auto [i, v, w] : g[u]) {
if (v != p && !used[v] && sz[v] > n / 2) {
return centroid(v, u, n);
}
}
return u;
}
void DFS1(int u, int p, int c) {
ancestors[u][cnt[u]++] = c;
dp_down[u] = has_shop[u] ? dist[u] : LLONG_MAX;
for (auto [i, v, w] : g[u]) {
if (v != p && !used[v]) {
dist[v] = dist[u] + w;
DFS1(v, u, c);
dp_down[u] = min(dp_down[u], dp_down[v]);
}
}
}
void DFS2(int u, int p, int c) {
long long Min = LLONG_MAX, Smin = LLONG_MAX;
for (auto [i, v, w] : g[u]) {
if (!used[v]) {
Smin = min(Smin, dp_down[v]);
if (Smin < Min) {
swap(Smin, Min);
}
}
}
for (auto [i, v, w] : g[u]) {
if (v != p && !used[v]) {
auto tmp1 = dp_down[u], tmp2 = dp_down[v];
dp_down[u] = min(has_shop[u] ? dist[u] : LLONG_MAX, dp_down[v] == Min ? Smin : Min);
dp_down[v] = min(dp_down[v], dp_down[u]);
min_excluding[c][i] = dp_down[u];
DFS2(v, u, c);
dp_down[u] = tmp1;
dp_down[v] = tmp2;
}
}
}
void _build_centroids(int u) {
sizes(u, -1);
dist[u] = 0;
DFS1(u, -1, u);
dp_val[u] = dp_down[u];
dp_up[u] = has_shop[u] ? 0 : LLONG_MAX;
DFS2(u, -1, u);
used[u] = true;
for (auto [i, v, w] : g[u]) {
if (!used[v]) {
int C = centroid(v, u, sz[v]);
_build_centroids(C);
}
}
}
void build_centroids() {
memset(ancestors, -1, sizeof ancestors);
memset(used, 0, sizeof used);
memset(cnt, 0, sizeof cnt);
sizes(0, -1);
_build_centroids(centroid(0, -1, sz[0]));
}
void solve() {
int n, s, q, e;
cin >> n >> s >> q >> e;
e--;
for (int i = 0; i < n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
edges[i][0] = u, edges[i][1] = v, edges[i][2] = w;
g[u].emplace_back(i, v, w);
g[v].emplace_back(i, u, w);
}
for (int i = 0; i < s; i++) {
int C;
cin >> C;
has_shop[--C] = true;
}
build_lifting();
build_centroids();
while (q--) {
int I, R;
cin >> I >> R;
I--, R--;
if (!check(R, e, I)) {
cout << "escaped\n";
} else {
long long ans = LLONG_MAX;
for (int i = 0; i < cnt[R]; i++) {
if (!check(R, ancestors[R][i], I)) {
long long x;
if (!min_excluding[ancestors[R][i]].contains(I)) {
x = dp_val[ancestors[R][i]];
} else {
x = min_excluding[ancestors[R][i]][I];
}
if (x != LLONG_MAX) {
ans = min(ans, dis(ancestors[R][i], R) + x);
}
}
}
if (ans == LLONG_MAX) {
cout << "oo\n";
} else {
cout << ans << "\n";
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}