# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
380524 |
2021-03-22T07:20:07 Z |
badont |
Valley (BOI19_valley) |
C++14 |
|
320 ms |
61452 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<LL,LL> pii;
typedef pair<LL,pii> ppi;
typedef pair<pii,pii> ppp;
#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define mp make_pair
#define pb push_back
#define f first
#define s second
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {cout << "["; F0R(i, v.size()) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
//var
const LL INF = 1e16;
LL T, n, s, q, st, t1, t2, t3, cc;
vector<pii> e[100005];
LL bl[100005][25], dp[100005][25], dep[100005], tin[100005], tout[100005], shop[100005], mnshopsub[100005];
pii ed[100005];
void dfs(LL g, LL p, LL d){
dep[g] = d;
bl[g][0] = p;
cc++; tin[g] = cc;
if(shop[g]) mnshopsub[g] = 0;
FOR(i, 17)
bl[g][i] = bl[bl[g][i-1]][i-1];
for(auto u : e[g]){
if(u.s == p) continue;
dfs(u.s, g, d + u.f);
mnshopsub[g] = min(mnshopsub[g], mnshopsub[u.s] + u.f);
}
cc++; tout[g] = cc;
}
void solve(){
cin >> n >> s >> q >> st;
FOR(i, n) mnshopsub[i] = INF;
FOR(i, n-1){
cin >> t1 >> t2 >> t3;
e[t1].pb({t3, t2});
e[t2].pb({t3, t1});
ed[i] = mp(t1, t2);
}
FOR(i, s){
cin >> t1;
shop[t1] = 1;
}
dfs(st, 0, 1);
FOR(i, n) F0R(j, 18) dp[i][j] = INF;
FOR(i, n) dp[i][0] = mnshopsub[i];
FOR(j, 17) FOR(i, n){
dp[i][j] = min(dp[i][j], min(
dp[i][j-1], dp[bl[i][j-1]][j-1] - dep[bl[i][j-1]] + dep[i]
));
}
FOR(i, n-1){
if(dep[ed[i].f] > dep[ed[i].s])
swap(ed[i].f, ed[i].s);
}
while(q--){
cin >> t1 >> t2;
LL tt = t1;
t1 = ed[t1].s;
if(tin[t2] < tin[t1] || tout[t2] > tout[t1]){
cout << "escaped\n";
continue;
}
t1 = ed[tt].f;
LL res = INF, ad = 0;
for(int j = 17; j>=0; j--){
if(dep[bl[t2][j]] < dep[t1]) continue;
res = min(res, dp[t2][j] + ad);
ad += dep[t2] - dep[bl[t2][j]];
t2 = bl[t2][j];
}
if(res >= INF){
cout << "oo" << '\n';
continue;
}
cout << res << '\n';
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
T = 1;
//cin >> T;
FOR(t, T)
solve();
cout.flush();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2796 KB |
Output is correct |
2 |
Correct |
6 ms |
2924 KB |
Output is correct |
3 |
Correct |
5 ms |
2924 KB |
Output is correct |
4 |
Correct |
4 ms |
2944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2796 KB |
Output is correct |
2 |
Correct |
6 ms |
2924 KB |
Output is correct |
3 |
Correct |
5 ms |
2924 KB |
Output is correct |
4 |
Correct |
4 ms |
2944 KB |
Output is correct |
5 |
Correct |
3 ms |
3308 KB |
Output is correct |
6 |
Correct |
3 ms |
3308 KB |
Output is correct |
7 |
Correct |
3 ms |
3308 KB |
Output is correct |
8 |
Correct |
3 ms |
3308 KB |
Output is correct |
9 |
Correct |
3 ms |
3308 KB |
Output is correct |
10 |
Correct |
3 ms |
3308 KB |
Output is correct |
11 |
Correct |
4 ms |
3308 KB |
Output is correct |
12 |
Correct |
4 ms |
3308 KB |
Output is correct |
13 |
Correct |
3 ms |
3308 KB |
Output is correct |
14 |
Correct |
3 ms |
3308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
219 ms |
53228 KB |
Output is correct |
2 |
Correct |
241 ms |
52972 KB |
Output is correct |
3 |
Correct |
237 ms |
53228 KB |
Output is correct |
4 |
Correct |
274 ms |
55040 KB |
Output is correct |
5 |
Correct |
269 ms |
55276 KB |
Output is correct |
6 |
Correct |
298 ms |
57256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2796 KB |
Output is correct |
2 |
Correct |
6 ms |
2924 KB |
Output is correct |
3 |
Correct |
5 ms |
2924 KB |
Output is correct |
4 |
Correct |
4 ms |
2944 KB |
Output is correct |
5 |
Correct |
3 ms |
3308 KB |
Output is correct |
6 |
Correct |
3 ms |
3308 KB |
Output is correct |
7 |
Correct |
3 ms |
3308 KB |
Output is correct |
8 |
Correct |
3 ms |
3308 KB |
Output is correct |
9 |
Correct |
3 ms |
3308 KB |
Output is correct |
10 |
Correct |
3 ms |
3308 KB |
Output is correct |
11 |
Correct |
4 ms |
3308 KB |
Output is correct |
12 |
Correct |
4 ms |
3308 KB |
Output is correct |
13 |
Correct |
3 ms |
3308 KB |
Output is correct |
14 |
Correct |
3 ms |
3308 KB |
Output is correct |
15 |
Correct |
219 ms |
53228 KB |
Output is correct |
16 |
Correct |
241 ms |
52972 KB |
Output is correct |
17 |
Correct |
237 ms |
53228 KB |
Output is correct |
18 |
Correct |
274 ms |
55040 KB |
Output is correct |
19 |
Correct |
269 ms |
55276 KB |
Output is correct |
20 |
Correct |
298 ms |
57256 KB |
Output is correct |
21 |
Correct |
208 ms |
55856 KB |
Output is correct |
22 |
Correct |
223 ms |
55660 KB |
Output is correct |
23 |
Correct |
240 ms |
55660 KB |
Output is correct |
24 |
Correct |
274 ms |
57836 KB |
Output is correct |
25 |
Correct |
282 ms |
60780 KB |
Output is correct |
26 |
Correct |
230 ms |
56044 KB |
Output is correct |
27 |
Correct |
228 ms |
55916 KB |
Output is correct |
28 |
Correct |
244 ms |
56172 KB |
Output is correct |
29 |
Correct |
285 ms |
57580 KB |
Output is correct |
30 |
Correct |
320 ms |
59116 KB |
Output is correct |
31 |
Correct |
201 ms |
56556 KB |
Output is correct |
32 |
Correct |
231 ms |
56556 KB |
Output is correct |
33 |
Correct |
246 ms |
56684 KB |
Output is correct |
34 |
Correct |
278 ms |
58604 KB |
Output is correct |
35 |
Correct |
296 ms |
61452 KB |
Output is correct |
36 |
Correct |
268 ms |
58476 KB |
Output is correct |