#include <bits/stdc++.h>
using namespace std;
int par[100005][17], dep[100005], l[100005], r[100005];
vector<pair<int, long long> > adj[100005];
long long dp[100005][17], dis[100005];
pair<int, int> edge[100005];
bool shop[100005];
vector<int> vec;
void dfs(int u, int p)
{
vec.push_back(u);
if (shop[u])
dp[u][0]=dis[u];
else
dp[u][0]=2e18;
par[u][0]=p;
for (int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first;
long long w=adj[u][i].second;
if (v!=p)
{
dis[v]=dis[u]+w;
dep[v]=dep[u]+1;
dfs(v, u);
dp[u][0]=min(dp[u][0], dp[v][0]);
}
}
vec.push_back(u);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, s, q, e;
cin >> n >> s >> q >> e;
for (int i=1; i<n; i++)
{
int u, v;
long long w;
cin >> u >> v >> w;
edge[i]={u, v};
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for (int i=1; i<=s; i++)
{
int u;
cin >> u;
shop[u]=1;
}
dfs(e, e);
for (int i=1; i<=n; i++)
dp[i][0]-=dis[i]*2;
for (int i=1; i<=16; i++)
{
for (int j=1; j<=n; j++)
{
dp[j][i]=min(dp[j][i-1], dp[par[j][i-1]][i-1]);
par[j][i]=par[par[j][i-1]][i-1];
}
}
for (int i=0; i<n*2; i++)
if (!l[vec[i]])
l[vec[i]]=i+1;
for (int i=n*2-1; i>=0; i--)
if (!r[vec[i]])
r[vec[i]]=i+1;
for (int i=1; i<=q; i++)
{
int x, y;
cin >> x >> y;
if (dep[edge[x].first]>dep[edge[x].second])
x=edge[x].first;
else
x=edge[x].second;
if (l[x]<=l[y] && r[y]<=r[x])
{
int d=dep[y]-dep[x]+1, cur=y;
long long mn=2e18;
for (int i=0; i<=16; i++)
{
if (d&(1<<i))
{
mn=min(mn, dp[cur][i]);
cur=par[cur][i];
}
}
if (mn<1e18)
cout << mn+dis[y] << '\n';
else
cout << "oo\n";
}
else
cout << "escaped\n";
}
return 0;
}
Compilation message
valley.cpp: In function 'void dfs(int, int)':
valley.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int i=0; i<adj[u].size(); i++)
| ~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2772 KB |
Output is correct |
2 |
Correct |
4 ms |
2772 KB |
Output is correct |
3 |
Correct |
3 ms |
2772 KB |
Output is correct |
4 |
Correct |
4 ms |
2772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2772 KB |
Output is correct |
2 |
Correct |
4 ms |
2772 KB |
Output is correct |
3 |
Correct |
3 ms |
2772 KB |
Output is correct |
4 |
Correct |
4 ms |
2772 KB |
Output is correct |
5 |
Correct |
2 ms |
3028 KB |
Output is correct |
6 |
Correct |
3 ms |
3028 KB |
Output is correct |
7 |
Correct |
2 ms |
3028 KB |
Output is correct |
8 |
Correct |
3 ms |
3028 KB |
Output is correct |
9 |
Correct |
2 ms |
3028 KB |
Output is correct |
10 |
Correct |
3 ms |
3028 KB |
Output is correct |
11 |
Correct |
3 ms |
3004 KB |
Output is correct |
12 |
Correct |
3 ms |
3028 KB |
Output is correct |
13 |
Correct |
3 ms |
2952 KB |
Output is correct |
14 |
Correct |
3 ms |
3028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
134 ms |
36012 KB |
Output is correct |
2 |
Correct |
143 ms |
35784 KB |
Output is correct |
3 |
Correct |
156 ms |
35956 KB |
Output is correct |
4 |
Correct |
154 ms |
37828 KB |
Output is correct |
5 |
Correct |
159 ms |
38052 KB |
Output is correct |
6 |
Correct |
190 ms |
40132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2772 KB |
Output is correct |
2 |
Correct |
4 ms |
2772 KB |
Output is correct |
3 |
Correct |
3 ms |
2772 KB |
Output is correct |
4 |
Correct |
4 ms |
2772 KB |
Output is correct |
5 |
Correct |
2 ms |
3028 KB |
Output is correct |
6 |
Correct |
3 ms |
3028 KB |
Output is correct |
7 |
Correct |
2 ms |
3028 KB |
Output is correct |
8 |
Correct |
3 ms |
3028 KB |
Output is correct |
9 |
Correct |
2 ms |
3028 KB |
Output is correct |
10 |
Correct |
3 ms |
3028 KB |
Output is correct |
11 |
Correct |
3 ms |
3004 KB |
Output is correct |
12 |
Correct |
3 ms |
3028 KB |
Output is correct |
13 |
Correct |
3 ms |
2952 KB |
Output is correct |
14 |
Correct |
3 ms |
3028 KB |
Output is correct |
15 |
Correct |
134 ms |
36012 KB |
Output is correct |
16 |
Correct |
143 ms |
35784 KB |
Output is correct |
17 |
Correct |
156 ms |
35956 KB |
Output is correct |
18 |
Correct |
154 ms |
37828 KB |
Output is correct |
19 |
Correct |
159 ms |
38052 KB |
Output is correct |
20 |
Correct |
190 ms |
40132 KB |
Output is correct |
21 |
Correct |
141 ms |
35300 KB |
Output is correct |
22 |
Correct |
151 ms |
35244 KB |
Output is correct |
23 |
Correct |
153 ms |
35344 KB |
Output is correct |
24 |
Correct |
146 ms |
37560 KB |
Output is correct |
25 |
Correct |
167 ms |
40524 KB |
Output is correct |
26 |
Correct |
130 ms |
35424 KB |
Output is correct |
27 |
Correct |
148 ms |
35340 KB |
Output is correct |
28 |
Correct |
141 ms |
35536 KB |
Output is correct |
29 |
Correct |
182 ms |
37008 KB |
Output is correct |
30 |
Correct |
163 ms |
38612 KB |
Output is correct |
31 |
Correct |
124 ms |
35492 KB |
Output is correct |
32 |
Correct |
156 ms |
35452 KB |
Output is correct |
33 |
Correct |
145 ms |
35712 KB |
Output is correct |
34 |
Correct |
162 ms |
37568 KB |
Output is correct |
35 |
Correct |
174 ms |
40512 KB |
Output is correct |
36 |
Correct |
160 ms |
37548 KB |
Output is correct |