#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <ll, ll>;
using pil = pair <ll, ll>;
using pli = pair <ll, ll>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll maxN = 2e5 + 1;
ll n, s, q, e;
ll cnt = 1;
ll a[maxN], pos[maxN], dis[maxN], rpos[maxN], child[maxN];
ll depth[maxN];
bool isshop[maxN];
vector <pii> adj[maxN];
ll st[maxN * 4];
pii edge[maxN];
void build(ll id = 1, ll l = 1, ll r = n){
if (l == r){
st[id] = isshop[rpos[l]] ? dis[rpos[l]] : inf;
return;
}
ll mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
st[id] = min(st[id * 2], st[id * 2 + 1]);
}
ll get(ll id, ll i, ll j, ll l = 1, ll r = n){
if (r < i || l > j) return inf;
if (i <= l && r <= j) return st[id];
ll mid = (l + r) / 2;
return min(get(id * 2, i, j, l, mid), get(id * 2 + 1, i, j, mid + 1, r));
}
void pre_dfs(ll u, ll p){
pos[u] = cnt;
rpos[cnt++] = u;
depth[u] = depth[p] + 1;
for (const pii &i: adj[u]){
if (i.fi == p) continue;
dis[i.fi] = dis[u] + i.se;
pre_dfs(i.fi, u);
child[u] += child[i.fi] + 1;
}
}
pii stble[maxN][20];
void dfs(ll u, ll p){
stble[u][0].fi = get(1, pos[u], pos[u] + child[u]);
if (stble[u][0].fi != inf) stble[u][0].fi -= dis[u];
stble[u][0].se = p;
for (ll i = 1; i < 20; ++i){
stble[u][i].fi = min(stble[u][i - 1].fi, stble[stble[u][i - 1].se][i - 1].fi + dis[u] - dis[stble[u][i - 1].se]);
stble[u][i].se = stble[stble[u][i - 1].se][i - 1].se;
}
for (const pii &i: adj[u]){
if (i.fi == p) continue;
dfs(i.fi, u);
}
}
ll findshop(ll u, ll v){
ll k = depth[u] - depth[v];
ll uu = u;
ll ans = inf;
for (ll i = 19; i >= 0; --i){
if (depth[stble[u][i].se] >= depth[v] - 1){
ans = min(ans, stble[u][i].fi + dis[uu] - dis[u]);
u = stble[u][i].se;
}
}
return ans;
}
void Init(){
cin >> n >> s >> q >> e;
for (ll i = 1; i < n; ++i){
ll u, v, w;
cin >> u >> v >> w;
edge[i] = {u, v};
adj[u].pb({v, w});
adj[v].pb({u, w});
}
for (ll i = 1; i <= s; ++i){
ll t; cin >> t;
isshop[t] = 1;
}
for (ll i = 0; i <= n; ++i){
for (ll j = 0; j < 20; ++j) stble[i][j] = {inf, 0};
}
pre_dfs(e, 0);
build();
dfs(e, 0);
while (q--){
ll i, r;
cin >> i >> r;
ll u, v;
u = dis[edge[i].fi] < dis[edge[i].se] ? edge[i].fi : edge[i].se;
v = u ^ edge[i].fi ^ edge[i].se;
if (pos[r] < pos[v] || pos[r] > pos[v] + child[v]){
cout << "escaped\n";
}
else{
ll tem = findshop(r, v);
if (tem >= inf) cout << "oo\n";
else cout << tem << "\n";
}
}
}
int main(){
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
//freopen(taskname".out", "w", stdout);
}
faster;
ll tt = 1;
//cin >> tt;
while (tt--){
Init();
}
}
Compilation message
valley.cpp: In function 'll findshop(ll, ll)':
valley.cpp:84:8: warning: unused variable 'k' [-Wunused-variable]
84 | ll k = depth[u] - depth[v];
| ^
valley.cpp: In function 'int main()':
valley.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
135 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5204 KB |
Output is correct |
2 |
Correct |
5 ms |
5204 KB |
Output is correct |
3 |
Correct |
5 ms |
5204 KB |
Output is correct |
4 |
Correct |
5 ms |
5176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5204 KB |
Output is correct |
2 |
Correct |
5 ms |
5204 KB |
Output is correct |
3 |
Correct |
5 ms |
5204 KB |
Output is correct |
4 |
Correct |
5 ms |
5176 KB |
Output is correct |
5 |
Correct |
5 ms |
5560 KB |
Output is correct |
6 |
Correct |
3 ms |
5460 KB |
Output is correct |
7 |
Correct |
4 ms |
5460 KB |
Output is correct |
8 |
Correct |
5 ms |
5460 KB |
Output is correct |
9 |
Correct |
5 ms |
5460 KB |
Output is correct |
10 |
Correct |
4 ms |
5516 KB |
Output is correct |
11 |
Correct |
4 ms |
5460 KB |
Output is correct |
12 |
Correct |
5 ms |
5564 KB |
Output is correct |
13 |
Correct |
4 ms |
5500 KB |
Output is correct |
14 |
Correct |
4 ms |
5460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
176 ms |
50700 KB |
Output is correct |
2 |
Correct |
212 ms |
53452 KB |
Output is correct |
3 |
Correct |
208 ms |
53612 KB |
Output is correct |
4 |
Correct |
246 ms |
55116 KB |
Output is correct |
5 |
Correct |
223 ms |
55372 KB |
Output is correct |
6 |
Correct |
276 ms |
57020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5204 KB |
Output is correct |
2 |
Correct |
5 ms |
5204 KB |
Output is correct |
3 |
Correct |
5 ms |
5204 KB |
Output is correct |
4 |
Correct |
5 ms |
5176 KB |
Output is correct |
5 |
Correct |
5 ms |
5560 KB |
Output is correct |
6 |
Correct |
3 ms |
5460 KB |
Output is correct |
7 |
Correct |
4 ms |
5460 KB |
Output is correct |
8 |
Correct |
5 ms |
5460 KB |
Output is correct |
9 |
Correct |
5 ms |
5460 KB |
Output is correct |
10 |
Correct |
4 ms |
5516 KB |
Output is correct |
11 |
Correct |
4 ms |
5460 KB |
Output is correct |
12 |
Correct |
5 ms |
5564 KB |
Output is correct |
13 |
Correct |
4 ms |
5500 KB |
Output is correct |
14 |
Correct |
4 ms |
5460 KB |
Output is correct |
15 |
Correct |
176 ms |
50700 KB |
Output is correct |
16 |
Correct |
212 ms |
53452 KB |
Output is correct |
17 |
Correct |
208 ms |
53612 KB |
Output is correct |
18 |
Correct |
246 ms |
55116 KB |
Output is correct |
19 |
Correct |
223 ms |
55372 KB |
Output is correct |
20 |
Correct |
276 ms |
57020 KB |
Output is correct |
21 |
Correct |
166 ms |
52944 KB |
Output is correct |
22 |
Correct |
211 ms |
52820 KB |
Output is correct |
23 |
Correct |
199 ms |
52968 KB |
Output is correct |
24 |
Correct |
263 ms |
54868 KB |
Output is correct |
25 |
Correct |
239 ms |
57460 KB |
Output is correct |
26 |
Correct |
167 ms |
53068 KB |
Output is correct |
27 |
Correct |
189 ms |
52924 KB |
Output is correct |
28 |
Correct |
197 ms |
53192 KB |
Output is correct |
29 |
Correct |
247 ms |
54276 KB |
Output is correct |
30 |
Correct |
270 ms |
55740 KB |
Output is correct |
31 |
Correct |
188 ms |
53188 KB |
Output is correct |
32 |
Correct |
203 ms |
52940 KB |
Output is correct |
33 |
Correct |
232 ms |
53312 KB |
Output is correct |
34 |
Correct |
250 ms |
54800 KB |
Output is correct |
35 |
Correct |
239 ms |
57136 KB |
Output is correct |
36 |
Correct |
227 ms |
54736 KB |
Output is correct |