#include <bits/stdc++.h>
#define pii pair<int,int>
#define pil pair<int,long long>
#define vii vector<pii>
#define vil vector<pil>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const ll INF = 1e18 + 7;
int par[19][MAXN], dep[MAXN];
int sh[MAXN], mrk[MAXN];
ll depth[MAXN], nx2[MAXN], nxPar[19][MAXN];
vil adj[MAXN];
pair<pii,ll> edg[MAXN];
void dfs(int u, int p, ll d, int d2) {
depth[u] = d;
dep[u] = d2;
if (mrk[u])
nx2[u] = d;
else
nx2[u] = INF;
for (pil nx: adj[u]) {
int v; ll w;
tie(v, w) = nx;
if (v == p) continue;
par[0][v] = u;
dfs(v, u, d+w, d2+1);
nx2[u] = min(nx2[u], nx2[v]);
}
}
int lca(int u, int v) {
if (dep[u] > dep[v]) swap(u, v);
int d = dep[v]-dep[u];
for (int i = 0; i < 19; i++)
if ((d >> i) & 1)
v = par[i][v];
if (u == v) return u;
for (int i = 18; i > -1; i--)
if (par[i][u] != par[i][v])
v = par[i][v], u = par[i][u];
return par[0][u];
}
int main() {
int n, s, q, e;
scanf("%d %d %d %d", &n, &s, &q, &e);
e--;
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
u--, v--;
adj[u].pb(mp(v, w));
adj[v].pb(mp(u, w));
edg[i-1]=mp(mp(u,v),w);
}
for (int j = 0; j < s; j++) {
scanf("%d", &sh[j]);
mrk[--sh[j]] = 1;
}
dfs(e, -1, 0, 0);
for (int i = 0; i < n; i++)
if (nx2[i] != INF)
nx2[i] -= 2*depth[i];
for (int i = 0; i < n; i++)
nxPar[0][i] = min(nx2[par[0][i]], nx2[i]);
for (int i = 1; i < 19; i++) {
for (int j = 0; j < n; j++) {
par[i][j] = par[i-1][par[i-1][j]];
nxPar[i][j] = min(nxPar[i-1][j],nxPar[i-1][par[i-1][j]]);
}
}
while (q--) {
int i, r;
scanf("%d %d", &i, &r);
i--, r--;
int u, v;
tie(u,v)=edg[i].fi;
if (dep[u] < dep[v])
swap(u,v);
if (lca(r,u) != u) {
printf("escaped\n");
continue;
}
if (mrk[r]) {
printf("0\n");
continue;
}
int r0 = r;
ll ans = nx2[r];
int delta = dep[r] - dep[u];
for (int i = 18; i > -1; i--)
if ((delta >> i) & 1) {
ans = min(ans, nxPar[i][r]);
r = par[i][r];
}
if (ans == INF)
printf("oo\n");
else
printf("%lld\n", ans+depth[r0]);
}
return 0;
}
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &n, &s, &q, &e);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &sh[j]);
~~~~~^~~~~~~~~~~~~~
valley.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &i, &r);
~~~~~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
2936 KB |
Output is correct |
2 |
Correct |
8 ms |
2936 KB |
Output is correct |
3 |
Correct |
8 ms |
2936 KB |
Output is correct |
4 |
Correct |
8 ms |
2936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
2936 KB |
Output is correct |
2 |
Correct |
8 ms |
2936 KB |
Output is correct |
3 |
Correct |
8 ms |
2936 KB |
Output is correct |
4 |
Correct |
8 ms |
2936 KB |
Output is correct |
5 |
Correct |
5 ms |
3192 KB |
Output is correct |
6 |
Correct |
5 ms |
3192 KB |
Output is correct |
7 |
Correct |
5 ms |
3192 KB |
Output is correct |
8 |
Correct |
5 ms |
3192 KB |
Output is correct |
9 |
Correct |
5 ms |
3192 KB |
Output is correct |
10 |
Correct |
5 ms |
3192 KB |
Output is correct |
11 |
Correct |
5 ms |
3192 KB |
Output is correct |
12 |
Correct |
5 ms |
3192 KB |
Output is correct |
13 |
Correct |
6 ms |
3320 KB |
Output is correct |
14 |
Correct |
7 ms |
3192 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
229 ms |
35164 KB |
Output is correct |
2 |
Correct |
213 ms |
34936 KB |
Output is correct |
3 |
Correct |
229 ms |
35196 KB |
Output is correct |
4 |
Correct |
228 ms |
36984 KB |
Output is correct |
5 |
Correct |
243 ms |
37244 KB |
Output is correct |
6 |
Correct |
244 ms |
39356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
2936 KB |
Output is correct |
2 |
Correct |
8 ms |
2936 KB |
Output is correct |
3 |
Correct |
8 ms |
2936 KB |
Output is correct |
4 |
Correct |
8 ms |
2936 KB |
Output is correct |
5 |
Correct |
5 ms |
3192 KB |
Output is correct |
6 |
Correct |
5 ms |
3192 KB |
Output is correct |
7 |
Correct |
5 ms |
3192 KB |
Output is correct |
8 |
Correct |
5 ms |
3192 KB |
Output is correct |
9 |
Correct |
5 ms |
3192 KB |
Output is correct |
10 |
Correct |
5 ms |
3192 KB |
Output is correct |
11 |
Correct |
5 ms |
3192 KB |
Output is correct |
12 |
Correct |
5 ms |
3192 KB |
Output is correct |
13 |
Correct |
6 ms |
3320 KB |
Output is correct |
14 |
Correct |
7 ms |
3192 KB |
Output is correct |
15 |
Correct |
229 ms |
35164 KB |
Output is correct |
16 |
Correct |
213 ms |
34936 KB |
Output is correct |
17 |
Correct |
229 ms |
35196 KB |
Output is correct |
18 |
Correct |
228 ms |
36984 KB |
Output is correct |
19 |
Correct |
243 ms |
37244 KB |
Output is correct |
20 |
Correct |
244 ms |
39356 KB |
Output is correct |
21 |
Correct |
175 ms |
34424 KB |
Output is correct |
22 |
Correct |
235 ms |
34260 KB |
Output is correct |
23 |
Correct |
202 ms |
34424 KB |
Output is correct |
24 |
Correct |
224 ms |
36512 KB |
Output is correct |
25 |
Correct |
256 ms |
39544 KB |
Output is correct |
26 |
Correct |
179 ms |
34680 KB |
Output is correct |
27 |
Correct |
191 ms |
34512 KB |
Output is correct |
28 |
Correct |
218 ms |
34680 KB |
Output is correct |
29 |
Correct |
253 ms |
36216 KB |
Output is correct |
30 |
Correct |
289 ms |
37756 KB |
Output is correct |
31 |
Correct |
187 ms |
34812 KB |
Output is correct |
32 |
Correct |
205 ms |
34756 KB |
Output is correct |
33 |
Correct |
215 ms |
34992 KB |
Output is correct |
34 |
Correct |
236 ms |
36856 KB |
Output is correct |
35 |
Correct |
262 ms |
39772 KB |
Output is correct |
36 |
Correct |
214 ms |
37368 KB |
Output is correct |