# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
498012 |
2021-12-24T09:10:31 Z |
Nalrimet |
Valley (BOI19_valley) |
C++17 |
|
322 ms |
117764 KB |
#include<bits/stdc++.h>
//#pragma GCC optimization("g", on)
//#pragma GCC optimize ("inline")
//#pragma GCC optimization("03")
//#pragma GCC optimization("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popused,abm,mmx,avx,tune=native")
using namespace std;
const int N = 1e6 + 5;
const long long inf = 1e18;
const int K = 25;
#define ll long long
#define int long long
#define F first
#define S second
#define pb push_back
int n, s, q, e, p[N], a[N], b[N], dp[N], dist[N], tin[N], tout[N], timer, mn[N][50], up[N][50];
vector<pair<int, int>> g[N];
void dfs(int v, int pr){
tin[v] = timer++;
up[v][0] = pr;
for(auto to : g[v]){
if(to.F != pr){
dist[to.F] = dist[v] + to.S;
dfs(to.F, v);
p[v] = min(p[v], p[to.F] + to.S);
}
}
for(auto to : g[v]){
if(to.F != pr){
mn[to.F][0] = p[v] - dist[v];
}
}
// dp[v] = p[v] - dist[v];
tout[v] = timer++;
}
bool is(int a, int b){
if(tin[a] <= tin[b] && tout[b] <= tout[a]) return 1;
else return 0;
}
void build(int v, int pr){
for(int i = 1; i <= K; ++i){
up[v][i] = up[up[v][i - 1]][i - 1];
mn[v][i] = min(mn[v][i - 1], mn[up[v][i - 1]][i - 1]);
}
for(auto to : g[v])
if(to.F != pr)
build(to.F, v);
}
int lift(int u, int v){
int res = inf, x = v;
for(int i = K; i >= 0; --i){
// cout << u << ' ' << up[x][i] << '\n';
if(is(u, up[x][i])){
// cout << "Yes\n";
// cout << mn[x][i] << '\n';
res = min(res, mn[x][i]);
x = up[x][i];
}
}
res += dist[v];
res = min(res, p[v]);
return res;
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> s >> q >> e;
for(int i = 1; i <= n; ++i){
p[i] = inf;
}
for(int i = 1, u, v, w; i < n; ++i){
cin >> u >> v >> w;
g[u].pb({v, w});
g[v].pb({u, w});
a[i] = u;
b[i] = v;
}
for(int i = 1, j; i <= s; ++i){
cin >> j;
p[j] = 0;
}
dfs(e, -1);
build(e, -1);
while(q--){
int i, v, f;
cin >> i >> v;
if(up[a[i]][0] == b[i]) f = a[i];
else f = b[i];
if(!is(f, v)) cout << "escaped\n";
else {
int ans = lift(f, v);
if(ans >= 1e15) cout << "oo\n";
else cout << ans << '\n';
}
}
}
Compilation message
valley.cpp:77:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
77 | main() {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
24012 KB |
Output is correct |
2 |
Correct |
15 ms |
24012 KB |
Output is correct |
3 |
Correct |
17 ms |
24012 KB |
Output is correct |
4 |
Correct |
15 ms |
24012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
24012 KB |
Output is correct |
2 |
Correct |
15 ms |
24012 KB |
Output is correct |
3 |
Correct |
17 ms |
24012 KB |
Output is correct |
4 |
Correct |
15 ms |
24012 KB |
Output is correct |
5 |
Correct |
14 ms |
24644 KB |
Output is correct |
6 |
Correct |
13 ms |
24648 KB |
Output is correct |
7 |
Correct |
13 ms |
24652 KB |
Output is correct |
8 |
Correct |
13 ms |
24748 KB |
Output is correct |
9 |
Correct |
14 ms |
24720 KB |
Output is correct |
10 |
Correct |
13 ms |
24652 KB |
Output is correct |
11 |
Correct |
13 ms |
24724 KB |
Output is correct |
12 |
Correct |
13 ms |
24664 KB |
Output is correct |
13 |
Correct |
13 ms |
24648 KB |
Output is correct |
14 |
Correct |
13 ms |
24684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
208 ms |
112624 KB |
Output is correct |
2 |
Correct |
203 ms |
112416 KB |
Output is correct |
3 |
Correct |
226 ms |
112612 KB |
Output is correct |
4 |
Correct |
276 ms |
114552 KB |
Output is correct |
5 |
Correct |
222 ms |
114556 KB |
Output is correct |
6 |
Correct |
322 ms |
116764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
24012 KB |
Output is correct |
2 |
Correct |
15 ms |
24012 KB |
Output is correct |
3 |
Correct |
17 ms |
24012 KB |
Output is correct |
4 |
Correct |
15 ms |
24012 KB |
Output is correct |
5 |
Correct |
14 ms |
24644 KB |
Output is correct |
6 |
Correct |
13 ms |
24648 KB |
Output is correct |
7 |
Correct |
13 ms |
24652 KB |
Output is correct |
8 |
Correct |
13 ms |
24748 KB |
Output is correct |
9 |
Correct |
14 ms |
24720 KB |
Output is correct |
10 |
Correct |
13 ms |
24652 KB |
Output is correct |
11 |
Correct |
13 ms |
24724 KB |
Output is correct |
12 |
Correct |
13 ms |
24664 KB |
Output is correct |
13 |
Correct |
13 ms |
24648 KB |
Output is correct |
14 |
Correct |
13 ms |
24684 KB |
Output is correct |
15 |
Correct |
208 ms |
112624 KB |
Output is correct |
16 |
Correct |
203 ms |
112416 KB |
Output is correct |
17 |
Correct |
226 ms |
112612 KB |
Output is correct |
18 |
Correct |
276 ms |
114552 KB |
Output is correct |
19 |
Correct |
222 ms |
114556 KB |
Output is correct |
20 |
Correct |
322 ms |
116764 KB |
Output is correct |
21 |
Correct |
176 ms |
112664 KB |
Output is correct |
22 |
Correct |
190 ms |
112452 KB |
Output is correct |
23 |
Correct |
240 ms |
112708 KB |
Output is correct |
24 |
Correct |
247 ms |
114808 KB |
Output is correct |
25 |
Correct |
260 ms |
117764 KB |
Output is correct |
26 |
Correct |
199 ms |
112672 KB |
Output is correct |
27 |
Correct |
203 ms |
112460 KB |
Output is correct |
28 |
Correct |
202 ms |
112704 KB |
Output is correct |
29 |
Correct |
263 ms |
114172 KB |
Output is correct |
30 |
Correct |
265 ms |
115772 KB |
Output is correct |
31 |
Correct |
190 ms |
112616 KB |
Output is correct |
32 |
Correct |
204 ms |
112452 KB |
Output is correct |
33 |
Correct |
207 ms |
112768 KB |
Output is correct |
34 |
Correct |
259 ms |
114668 KB |
Output is correct |
35 |
Correct |
267 ms |
117652 KB |
Output is correct |
36 |
Correct |
225 ms |
115116 KB |
Output is correct |