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>
using namespace std;
#define int long long
const int N = 1e5 + 5, LG = 17, INF = 1e18;
vector<pair<int, int> > g[N];
bool shop[N];
int lift[LG][N], tin[N], tout[N], tim = 0;
int dist_in_subtree[N];
void dfs(int node, int par)
{
if(shop[node])
{
dist_in_subtree[node] = 0;
}
else
{
dist_in_subtree[node] = INF;
}
tin[node] = ++tim;
lift[0][node] = par;
for(auto [to, wt]: g[node])
{
if(to == par) continue;
dfs(to, node);
dist_in_subtree[node] = min(dist_in_subtree[node], dist_in_subtree[to] + wt);
}
tout[node] = tim;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, s, q, e;
cin >> n >> s >> q >> e;
vector<array<int, 3> > edges;
for(int i = 1; i < n; i++)
{
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
edges.push_back({u, v, w});
}
for(int i = 1; i <= s; i++)
{
int x;
cin >> x;
shop[x] = true;
}
dfs(e, 0);
for(int i = 1; i < LG; i++)
{
for(int j = 1; j <= n; j++)
{
lift[i][j] = lift[i - 1][lift[i - 1][j]];
}
}
for(int i = 1; i <= q; i++)
{
int idx, node;
cin >> idx >> node;
idx -= 1;
if(tin[edges[i][0]] <= tin[edges[i][1]])
{
swap(edges[i][0], edges[i][1]);
}
if(tin[edges[idx][0]] <= tin[node] && tout[node] <= tout[edges[idx][0]])
{
if(dist_in_subtree[edges[i][0]] >= INF)
{
cout << "oo\n";
}
else
{
cout << "0\n";
}
}
else
{
cout << "escaped\n";
}
}
}
# | 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... |