# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
130839 | 2019-07-16T06:55:43 Z | PeppaPig | Valley (BOI19_valley) | C++14 | 266 ms | 41436 KB |
#include <bits/stdc++.h> #define long long long #define pii pair<long, long> #define x first #define y second using namespace std; const int N = 1e5+5; int n, s, q, e; int u[N], v[N], w[N], in[N], out[N], pos[N]; int par[N][18], dep[N]; long d[N], dp[N], pre[N][18]; bitset<N> shop; vector<pii> g[N]; void gen_lca(int u, int p) { static int idx = 0; in[u] = ++idx, pos[idx] = u; dep[u] = dep[p] + 1, par[u][0] = p; if(shop[u]) dp[u] = d[u]; for(pii v : g[u]) if(v.x != p) { d[v.x] = d[u] + v.y; gen_lca(v.x, u); dp[u] = min(dp[u], dp[v.x]); } out[u] = idx; } int main() { fill_n(dp, N, 1e18), fill_n(pre[0], N * 18, 1e18); scanf("%d %d %d %d", &n, &s, &q, &e); for(int i = 1; i < n; i++) { scanf("%d %d %d", u + i, v + i, w + i); g[u[i]].emplace_back(v[i], w[i]); g[v[i]].emplace_back(u[i], w[i]); } for(int i = 1, a; i <= s; i++) scanf("%d", &a), shop[a] = true; gen_lca(e, 0); for(int i = 1; i <= n; i++) if(dp[i] != 1e18) pre[i][0] = dp[i] - 2 * d[i]; for(int t = 1; t <= n; t++) { int u = pos[t]; for(int i = 1; i <= 17; i++) { par[u][i] = par[par[u][i-1]][i-1]; pre[u][i] = min(pre[u][i-1], pre[par[u][i-1]][i-1]); } } for(int i = 1, a, b; i <= q; i++) { scanf("%d %d", &a, &b); int now = dep[u[a]] > dep[v[a]] ? u[a] : v[a]; if(in[now] > in[b] || out[b] > out[now]) { printf("escaped\n"); continue; } int dist = dep[b] - dep[now], u = b; long ans = 1e18; for(int i = 17; ~i; i--) if(dist >> i & 1) { ans = min(ans, pre[u][i]); u = par[u][i]; } ans = min(ans, pre[u][0]); if(ans >= 1e18) printf("oo\n"); else printf("%lld\n", ans + d[b]); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 17656 KB | Output is correct |
2 | Correct | 20 ms | 17784 KB | Output is correct |
3 | Correct | 20 ms | 17784 KB | Output is correct |
4 | Correct | 20 ms | 17784 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 17656 KB | Output is correct |
2 | Correct | 20 ms | 17784 KB | Output is correct |
3 | Correct | 20 ms | 17784 KB | Output is correct |
4 | Correct | 20 ms | 17784 KB | Output is correct |
5 | Correct | 18 ms | 17784 KB | Output is correct |
6 | Correct | 18 ms | 17784 KB | Output is correct |
7 | Correct | 18 ms | 17788 KB | Output is correct |
8 | Correct | 18 ms | 17712 KB | Output is correct |
9 | Correct | 18 ms | 17784 KB | Output is correct |
10 | Correct | 18 ms | 17784 KB | Output is correct |
11 | Correct | 21 ms | 17784 KB | Output is correct |
12 | Correct | 18 ms | 17784 KB | Output is correct |
13 | Correct | 18 ms | 17784 KB | Output is correct |
14 | Correct | 18 ms | 17784 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 209 ms | 34024 KB | Output is correct |
2 | Correct | 221 ms | 37684 KB | Output is correct |
3 | Correct | 228 ms | 37832 KB | Output is correct |
4 | Correct | 244 ms | 39288 KB | Output is correct |
5 | Correct | 228 ms | 39496 KB | Output is correct |
6 | Correct | 265 ms | 41156 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 17656 KB | Output is correct |
2 | Correct | 20 ms | 17784 KB | Output is correct |
3 | Correct | 20 ms | 17784 KB | Output is correct |
4 | Correct | 20 ms | 17784 KB | Output is correct |
5 | Correct | 18 ms | 17784 KB | Output is correct |
6 | Correct | 18 ms | 17784 KB | Output is correct |
7 | Correct | 18 ms | 17788 KB | Output is correct |
8 | Correct | 18 ms | 17712 KB | Output is correct |
9 | Correct | 18 ms | 17784 KB | Output is correct |
10 | Correct | 18 ms | 17784 KB | Output is correct |
11 | Correct | 21 ms | 17784 KB | Output is correct |
12 | Correct | 18 ms | 17784 KB | Output is correct |
13 | Correct | 18 ms | 17784 KB | Output is correct |
14 | Correct | 18 ms | 17784 KB | Output is correct |
15 | Correct | 209 ms | 34024 KB | Output is correct |
16 | Correct | 221 ms | 37684 KB | Output is correct |
17 | Correct | 228 ms | 37832 KB | Output is correct |
18 | Correct | 244 ms | 39288 KB | Output is correct |
19 | Correct | 228 ms | 39496 KB | Output is correct |
20 | Correct | 265 ms | 41156 KB | Output is correct |
21 | Correct | 191 ms | 37220 KB | Output is correct |
22 | Correct | 200 ms | 37164 KB | Output is correct |
23 | Correct | 203 ms | 37372 KB | Output is correct |
24 | Correct | 222 ms | 39032 KB | Output is correct |
25 | Correct | 266 ms | 41436 KB | Output is correct |
26 | Correct | 219 ms | 37236 KB | Output is correct |
27 | Correct | 202 ms | 37040 KB | Output is correct |
28 | Correct | 220 ms | 37328 KB | Output is correct |
29 | Correct | 234 ms | 38520 KB | Output is correct |
30 | Correct | 252 ms | 39928 KB | Output is correct |
31 | Correct | 192 ms | 36088 KB | Output is correct |
32 | Correct | 199 ms | 34040 KB | Output is correct |
33 | Correct | 225 ms | 34204 KB | Output is correct |
34 | Correct | 244 ms | 36384 KB | Output is correct |
35 | Correct | 234 ms | 38648 KB | Output is correct |
36 | Correct | 215 ms | 38776 KB | Output is correct |