이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const int LG = 20;
const ll inf = 1e16;
struct ura{
int x; ll c;
};
struct ura2{
int x, y;
} edges[N];
vector <ura> g[N];
int n, s, q, e;
int h[N];
ll d[N];
int dad[N][LG];
ll dpmini[N][LG];
int shop[N];
ll mini[N];
void dfs(int nod)
{
mini[nod] = inf;
if (shop[nod])
mini[nod] = d[nod];
for (auto p : g[nod])
{
int x = p.x;
ll c = p.c;
if (x == dad[nod][0])
continue;
dad[x][0] = nod;
h[x] = h[nod] + 1;
d[x] = d[nod] + c;
dfs(x);
mini[nod] = min(mini[nod], mini[x]);
}
}
void lifting()
{
for (int j = 1; j <= 19; j++)
{
for (int i = 1; i <= n; i++)
{
dad[i][j] = dad[dad[i][j - 1]][j - 1];
dpmini[i][j] = min(dpmini[i][j - 1], dpmini[dad[i][j - 1]][j - 1]);
}
}
}
int main()
{
cin >> n >> s >> q >> e;
for (int i = 1; i < n; i++)
{
int a, b, c;
cin >> a >> b >> c;
g[a].push_back({b, c});
g[b].push_back({a, c});
edges[i] = {a, b};
}
for (int i = 1; i <= s; i++)
{
int c;
cin >> c;
shop[c] = 1;
}
dfs(e);
for (int i = 1; i <= n; i++)
{
dpmini[i][0] = inf;
if (mini[i] != inf)
dpmini[i][0] = mini[i] = mini[i] - 2 * d[i];
}
lifting();
while(q--)
{
int ind, r;
cin >> ind >> r;
int a = edges[ind].x;
int b = edges[ind].y;
if (h[a] < h[b])
swap(a, b);
///verific daca r e in subarb a
int lg = 19; ll ans = inf;
b = r;
while (h[a] != h[b])
{
if (h[dad[b][lg]] >= h[a])
{
ans = min(ans, dpmini[b][lg]);
b = dad[b][lg];
}
lg--;
}
if (b != a)
{
cout << "escaped" << '\n';
continue;
}
ans = min(ans, dpmini[b][0]);
if (ans == inf)
cout << "oo\n";
else
cout << ans + d[r] << '\n';
}
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... |