# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
125007 | 2019-07-04T10:46:28 Z | gs14004 | Valley (BOI19_valley) | C++17 | 227 ms | 36992 KB |
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; using lint = long long; using pi = pair<int, int>; struct edg{ int s, e, x; }ed[MAXN]; vector<pi> gph[MAXN]; int n, m, q, r, din[MAXN], dout[MAXN], lvl[MAXN], piv; lint dp[MAXN], dep[MAXN]; int par[17][MAXN]; lint spt[17][MAXN]; bool sub(int s, int e){ return din[s] <= din[e] && dout[e] <= dout[s]; } void dfs(int x, int p){ din[x] = ++piv; for(auto &i : gph[x]){ if(i.second == p) continue; dep[i.second] = dep[x] + i.first; lvl[i.second] = lvl[x] + 1; par[0][i.second] = x; dfs(i.second, x); dp[x] = min(dp[x], dp[i.second] + i.first); } dout[x] = piv; } int main(){ scanf("%d %d %d %d",&n,&m,&q,&r); for(int i=1; i<n; i++){ scanf("%d %d %d",&ed[i].s,&ed[i].e,&ed[i].x); gph[ed[i].s].emplace_back(ed[i].x, ed[i].e); gph[ed[i].e].emplace_back(ed[i].x, ed[i].s); } memset(dp, 0x3f, sizeof(dp)); while(m--){ int x; scanf("%d",&x); dp[x] = 0; } dfs(r, -1); for(int i=1; i<n; i++){ if(par[0][ed[i].s] == ed[i].e) swap(ed[i].s, ed[i].e); } for(int i=1; i<=n; i++){ spt[0][i] = dp[i] - dep[i]; } for(int i=1; i<17; i++){ for(int j=1; j<=n; j++){ par[i][j] = par[i-1][par[i-1][j]]; spt[i][j] = min(spt[i-1][j], spt[i-1][par[i-1][j]]); } } while(q--){ int idx, pos; scanf("%d %d",&idx,&pos); idx = ed[idx].e; if(!sub(idx, pos)){ puts("escaped"); continue; } lint ret = 1e18; int step = lvl[pos] - lvl[idx] + 1; int opo = pos; for(int i=0; i<17; i++){ if((step >> i) & 1){ ret = min(ret, spt[i][pos]); pos = par[i][pos]; } } ret += dep[opo]; if(ret > 1e17) puts("oo"); else printf("%lld\n", ret); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 3804 KB | Output is correct |
2 | Correct | 8 ms | 3832 KB | Output is correct |
3 | Correct | 7 ms | 3836 KB | Output is correct |
4 | Correct | 8 ms | 3832 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 3804 KB | Output is correct |
2 | Correct | 8 ms | 3832 KB | Output is correct |
3 | Correct | 7 ms | 3836 KB | Output is correct |
4 | Correct | 8 ms | 3832 KB | Output is correct |
5 | Correct | 6 ms | 3932 KB | Output is correct |
6 | Correct | 6 ms | 3960 KB | Output is correct |
7 | Correct | 6 ms | 3960 KB | Output is correct |
8 | Correct | 6 ms | 3960 KB | Output is correct |
9 | Correct | 6 ms | 3960 KB | Output is correct |
10 | Correct | 6 ms | 3960 KB | Output is correct |
11 | Correct | 6 ms | 3960 KB | Output is correct |
12 | Correct | 6 ms | 3960 KB | Output is correct |
13 | Correct | 6 ms | 3960 KB | Output is correct |
14 | Correct | 6 ms | 3964 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 168 ms | 35064 KB | Output is correct |
2 | Correct | 192 ms | 34680 KB | Output is correct |
3 | Correct | 190 ms | 34592 KB | Output is correct |
4 | Correct | 215 ms | 35668 KB | Output is correct |
5 | Correct | 189 ms | 35832 KB | Output is correct |
6 | Correct | 227 ms | 36684 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 3804 KB | Output is correct |
2 | Correct | 8 ms | 3832 KB | Output is correct |
3 | Correct | 7 ms | 3836 KB | Output is correct |
4 | Correct | 8 ms | 3832 KB | Output is correct |
5 | Correct | 6 ms | 3932 KB | Output is correct |
6 | Correct | 6 ms | 3960 KB | Output is correct |
7 | Correct | 6 ms | 3960 KB | Output is correct |
8 | Correct | 6 ms | 3960 KB | Output is correct |
9 | Correct | 6 ms | 3960 KB | Output is correct |
10 | Correct | 6 ms | 3960 KB | Output is correct |
11 | Correct | 6 ms | 3960 KB | Output is correct |
12 | Correct | 6 ms | 3960 KB | Output is correct |
13 | Correct | 6 ms | 3960 KB | Output is correct |
14 | Correct | 6 ms | 3964 KB | Output is correct |
15 | Correct | 168 ms | 35064 KB | Output is correct |
16 | Correct | 192 ms | 34680 KB | Output is correct |
17 | Correct | 190 ms | 34592 KB | Output is correct |
18 | Correct | 215 ms | 35668 KB | Output is correct |
19 | Correct | 189 ms | 35832 KB | Output is correct |
20 | Correct | 227 ms | 36684 KB | Output is correct |
21 | Correct | 150 ms | 34424 KB | Output is correct |
22 | Correct | 161 ms | 34012 KB | Output is correct |
23 | Correct | 168 ms | 34176 KB | Output is correct |
24 | Correct | 181 ms | 35192 KB | Output is correct |
25 | Correct | 193 ms | 36992 KB | Output is correct |
26 | Correct | 191 ms | 34552 KB | Output is correct |
27 | Correct | 161 ms | 34040 KB | Output is correct |
28 | Correct | 171 ms | 34012 KB | Output is correct |
29 | Correct | 189 ms | 34936 KB | Output is correct |
30 | Correct | 220 ms | 35964 KB | Output is correct |
31 | Correct | 157 ms | 33396 KB | Output is correct |
32 | Correct | 173 ms | 30960 KB | Output is correct |
33 | Correct | 170 ms | 30908 KB | Output is correct |
34 | Correct | 184 ms | 31964 KB | Output is correct |
35 | Correct | 193 ms | 33656 KB | Output is correct |
36 | Correct | 172 ms | 32504 KB | Output is correct |