This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
using ll = long long;
const int N = 100'000 + 10;
const ll INF = 1'000'000'000'000'000'000;
int n, numStores, q, escape;
tuple<int, int, int> edges[N];
int positionStore[N];
namespace sub12 {
bool check() {
return (1ll * n * q <= 10'000'000);
}
vector<vector<pair<int, int>>> g;
ll dist[N];
void solve() {
g.resize(n + 1);
while (q -- > 0) {
for (int u = 1; u <= n; ++ u) {
g[u].clear();
dist[u] = INF;
}
int path, curPosition; cin >> path >> curPosition;
for (int i = 1; i <= n - 1; ++ i) {
if (i == path) continue;
int u = get<0>(edges[i]), v = get<1>(edges[i]), w = get<2>(edges[i]);
g[u].push_back(make_pair(v, w));
g[v].push_back(make_pair(u, w));
}
queue<int> q;
q.push(curPosition);
dist[curPosition] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (const auto& x : g[u]) {
int v = x.first, w = x.second;
if (dist[v] < INF) continue;
dist[v] = dist[u] + w;
q.push(v);
}
}
if (dist[escape] < INF) {
cout << "escaped";
}
else {
ll res = INF;
for (int i = 1; i <= numStores; ++ i) {
res = min(res, dist[positionStore[i]]);
}
if (res >= INF) {
cout << "oo";
}
else {
cout << res;
}
}
cout << '\n';
}
}
}
namespace sub3 {
bool check() {
return (numStores == n);
}
vector<vector<int>> g;
int Lg, dist[N], parent[20][N];
int cnt, in[N], out[N];
void dfs(int u, int p) {
in[u] = ++ cnt;
for (const auto& v : g[u]) {
if (v == p) continue;
parent[0][v] = u;
dist[v] = dist[u] + 1;
dfs(v, u);
}
out[u] = cnt;
};
int lca(int u, int v) {
if (dist[u] < dist[v]) swap(u, v);
int delta = dist[u] - dist[v];
for (int lg = Lg; lg >= 0; -- lg) {
if (((delta >> lg) & 1)) {
u = parent[lg][u];
}
}
if (u == v) return u;
for (int lg = Lg; lg >= 0; -- lg) {
if (parent[lg][u] != parent[lg][v]) {
u = parent[lg][u];
v = parent[lg][v];
}
}
return parent[0][u];
}
bool isChild(int u, int p) {
return in[p] <= in[u] && out[u] <= out[p];
}
void solve() {
g.resize(n + 1);
for (int i = 1; i <= n - 1; ++ i) {
int u = get<0>(edges[i]), v = get<1>(edges[i]);
g[u].push_back(v);
g[v].push_back(u);
}
Lg = __lg(n);
dist[1] = 1; dfs(1, 0);
for (int lg = 1; lg <= Lg; ++ lg) {
for (int u = 1; u <= n; ++ u) {
parent[lg][u] = parent[lg - 1][parent[lg - 1][u]];
}
}
for (int i = 1; i <= n - 1; ++ i) {
int u = get<0>(edges[i]), v = get<1>(edges[i]);
if (in[u] > in[v]) swap(u, v);
edges[i] = make_tuple(u, v, get<2>(edges[i]));
}
while (q -- > 0) {
int path, curPosition; cin >> path >> curPosition;
int anc = lca(curPosition, escape);
int u = get<0>(edges[path]);
int v = get<1>(edges[path]);
if (isChild(u, anc) && ((isChild(curPosition, u) && isChild(curPosition, v)) || (isChild(escape, u) && isChild(escape, v)))) {
cout << 0;
}
else {
cout << "escaped";
}
cout << '\n';
}
}
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
cin >> n >> numStores >> q >> escape;
for (int i = 1; i <= n - 1; ++ i) {
int u, v, w; cin >> u >> v >> w;
edges[i] = make_tuple(u, v, w);
}
for (int i = 1; i <= numStores; ++ i) cin >> positionStore[i];
if (sub12::check()) {
sub12::solve();
return 0;
}
if (sub3::check()) {
sub3::solve();
return 0;
}
return (0 ^ 0);
}
/// Code by vuavisao
# | 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... |