/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e5 + 10, maxlog = 20;
const ll inf = 1e18;
int n, s, q, e;
bool shop[maxn];
vector < pair < int, ll > > g[maxn];
int in[maxn], out[maxn], timer, lvl[maxn];
ll dp[maxn], cl[maxn], depth[maxn], jump[maxn][maxlog], mx[maxn][maxlog];
/// + depth[u] - 2 * depth[v]
void dfs(int v, int p)
{
in[v] = ++ timer;
cl[v] = inf;
for (pair < int, ll > nb : g[v])
{
int u = nb.first;
if (u == p)
continue;
lvl[u] = lvl[v] + 1;
depth[u] = depth[v] + nb.second;
dfs(u, v);
if (cl[u] < cl[v])
cl[v] = cl[u];
}
if (shop[v])
cl[v] = depth[v];
dp[v] = cl[v] - 2 * depth[v];
jump[v][0] = p;
out[v] = timer;
}
bool in_subtree(int v, int u)
{
if (in[v] <= in[u] && out[v] >= out[u])
return true;
return false;
}
ll make_jump(int v, int len)
{
ll ans = dp[v];
for (int bit = maxlog - 1; bit >= 0; bit --)
{
if ((len & (1 << bit)) > 0)
{
ans = min(ans, mx[v][bit]), v = jump[v][bit];
}
}
return ans;
}
pair < int, int > edge[maxn];
void solve()
{
cin >> n >> s >> q >> e;
for (int i = 1; i < n; i ++)
{
int v, u;
ll w;
cin >> v >> u >> w;
g[v].push_back({u, w});
g[u].push_back({v, w});
edge[i] = {v, u};
}
for (int i = 1; i <= s; i ++)
{
int v;
cin >> v;
shop[v] = true;
}
dp[0] = inf;
dfs(e, 0);
for (int j = 0; j < maxlog; j ++)
mx[0][j] = inf;
for (int i = 1; i <= n; i ++)
mx[i][0] = dp[jump[i][0]];
for (int j = 1; j < maxlog; j ++)
{
for (int i = 1; i <= n; i ++)
{
jump[i][j] = jump[jump[i][j - 1]][j - 1];
mx[i][j] = min(mx[i][j - 1], mx[jump[i][j - 1]][j - 1]);
}
}
for (int i = 1; i < n; i ++)
if (lvl[edge[i].first] > lvl[edge[i].second])
swap(edge[i].first, edge[i].second);
for (int i = 1; i <= q; i ++)
{
int id, v;
cin >> id >> v;
if (in_subtree(edge[id].second, v))
{
int len = lvl[v] - lvl[edge[id].second];
ll ans = make_jump(v, len) + depth[v];
if (cl[edge[id].second] == inf)
cout << "oo" << endl;
else
cout << ans << endl;
}
else
cout << "escaped" << endl;
}
}
int main()
{
speed();
solve();
return 0;
}
Compilation message
valley.cpp: In function 'void solve()':
valley.cpp:98:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
98 | for (int j = 0; j < maxlog; j ++)
| ^~~
valley.cpp:101:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
101 | for (int i = 1; i <= n; i ++)
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2812 KB |
Output is correct |
2 |
Correct |
4 ms |
2900 KB |
Output is correct |
3 |
Correct |
4 ms |
2900 KB |
Output is correct |
4 |
Correct |
4 ms |
2900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2812 KB |
Output is correct |
2 |
Correct |
4 ms |
2900 KB |
Output is correct |
3 |
Correct |
4 ms |
2900 KB |
Output is correct |
4 |
Correct |
4 ms |
2900 KB |
Output is correct |
5 |
Correct |
2 ms |
3072 KB |
Output is correct |
6 |
Correct |
2 ms |
3156 KB |
Output is correct |
7 |
Correct |
3 ms |
3072 KB |
Output is correct |
8 |
Correct |
2 ms |
3156 KB |
Output is correct |
9 |
Correct |
3 ms |
3156 KB |
Output is correct |
10 |
Correct |
3 ms |
3076 KB |
Output is correct |
11 |
Correct |
3 ms |
3156 KB |
Output is correct |
12 |
Correct |
3 ms |
3116 KB |
Output is correct |
13 |
Correct |
3 ms |
3072 KB |
Output is correct |
14 |
Correct |
3 ms |
3156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
140 ms |
44580 KB |
Output is correct |
2 |
Correct |
161 ms |
45068 KB |
Output is correct |
3 |
Correct |
171 ms |
45260 KB |
Output is correct |
4 |
Correct |
175 ms |
47260 KB |
Output is correct |
5 |
Correct |
170 ms |
47348 KB |
Output is correct |
6 |
Correct |
180 ms |
49468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2812 KB |
Output is correct |
2 |
Correct |
4 ms |
2900 KB |
Output is correct |
3 |
Correct |
4 ms |
2900 KB |
Output is correct |
4 |
Correct |
4 ms |
2900 KB |
Output is correct |
5 |
Correct |
2 ms |
3072 KB |
Output is correct |
6 |
Correct |
2 ms |
3156 KB |
Output is correct |
7 |
Correct |
3 ms |
3072 KB |
Output is correct |
8 |
Correct |
2 ms |
3156 KB |
Output is correct |
9 |
Correct |
3 ms |
3156 KB |
Output is correct |
10 |
Correct |
3 ms |
3076 KB |
Output is correct |
11 |
Correct |
3 ms |
3156 KB |
Output is correct |
12 |
Correct |
3 ms |
3116 KB |
Output is correct |
13 |
Correct |
3 ms |
3072 KB |
Output is correct |
14 |
Correct |
3 ms |
3156 KB |
Output is correct |
15 |
Correct |
140 ms |
44580 KB |
Output is correct |
16 |
Correct |
161 ms |
45068 KB |
Output is correct |
17 |
Correct |
171 ms |
45260 KB |
Output is correct |
18 |
Correct |
175 ms |
47260 KB |
Output is correct |
19 |
Correct |
170 ms |
47348 KB |
Output is correct |
20 |
Correct |
180 ms |
49468 KB |
Output is correct |
21 |
Correct |
137 ms |
47332 KB |
Output is correct |
22 |
Correct |
155 ms |
47200 KB |
Output is correct |
23 |
Correct |
163 ms |
47320 KB |
Output is correct |
24 |
Correct |
149 ms |
49484 KB |
Output is correct |
25 |
Correct |
173 ms |
52532 KB |
Output is correct |
26 |
Correct |
130 ms |
47572 KB |
Output is correct |
27 |
Correct |
145 ms |
47320 KB |
Output is correct |
28 |
Correct |
169 ms |
47440 KB |
Output is correct |
29 |
Correct |
181 ms |
48968 KB |
Output is correct |
30 |
Correct |
184 ms |
50532 KB |
Output is correct |
31 |
Correct |
123 ms |
47496 KB |
Output is correct |
32 |
Correct |
138 ms |
47424 KB |
Output is correct |
33 |
Correct |
143 ms |
47592 KB |
Output is correct |
34 |
Correct |
168 ms |
49692 KB |
Output is correct |
35 |
Correct |
187 ms |
52440 KB |
Output is correct |
36 |
Correct |
148 ms |
49472 KB |
Output is correct |