# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
503728 |
2022-01-08T18:12:46 Z |
Arnch |
Valley (BOI19_valley) |
C++17 |
|
446 ms |
253248 KB |
// oooo
/*
be hengam shena mesle y dasto pa cholofti ~
bepa to masire dahane koose neyofti ~
;Amoo_Hasan;
*/
#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")
using namespace std;
typedef long long ll;
typedef long double ld;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
const ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969, Log = 22;
int n, s, q, e;
ll par[N][Log], ans[N][Log], ans_h[N][Log], h[N], d[N];
bool mark[N], S[N];
vector<pair<int, int> > G[N], vc;
void get_input() {
cin >>n >>s >>q >>e;
for(int i = 1; i <= n - 1; i++) {
int u, v, w; cin >>u >>v >>w;
vc.push_back({u, v});
G[u].push_back({v, w}), G[v].push_back({u, w});
}
for(int i = 0; i < s; i++) {
int u; cin >>u; S[u] = 1;
}
}
void dfs(int x, int p) {
mark[x] = 1, par[x][0] = p;
if(S[x]) d[x] = 0;
for(int i = 1; i < Log; i++) par[x][i] = par[par[x][i - 1]][i - 1];
for(auto i : G[x]) if(!mark[i.first]) {
h[i.first] = h[x] + 1;
dfs(i.first, x);
d[x] = min(d[x], d[i.first] + i.second);
}
}
void main_dfs(int x, int val) {
mark[x] = 1, ans[x][0] = d[x], ans_h[x][0] = val;
for(int i = 1; i < Log; i++) {
if(par[x][i] == 0) break;
ans_h[x][i] = ans_h[x][i - 1] + ans_h[par[x][i - 1]][i - 1];
ans[x][i] = min(ans[x][i - 1], ans[par[x][i - 1]][i - 1] + ans_h[x][i - 1]);
}
for(auto i : G[x]) if(!mark[i.first]) {
main_dfs(i.first, i.second);
}
}
int get_par(int x, int y) {
for(int i = 0; i < Log; i++)
if((y >> i) & 1)
x = par[x][i];
return x;
}
int lca(int x, int y) {
if(h[x] > h[y]) swap(x, y);
y = get_par(y, h[y] - h[x]);
if(x == y) return x;
for(int i = Log - 1; i >= 0; i--) {
if(par[x][i] != par[y][i]) {
x = par[x][i], y = par[y][i];
}
}
return par[x][0];
}
void solve() {
int e, u; cin >>e >>u;
e--;
int l = vc[e].first;
if(par[l][0] != vc[e].second) l = vc[e].second;
if(lca(l, u) != l) {
cout<<"escaped" <<'\n';
return;
}
l = par[l][0];
ll cnt = h[u] - h[l], sum = inf, eq = 0;
for(int i = 0; i < Log; i++) {
if((cnt >> i) & 1) {
sum = min(sum, ans[u][i] + eq);
eq += ans_h[u][i];
u = par[u][i];
}
}
if(sum >= inf) cout<<"oo" <<'\n';
else cout<<sum <<'\n';
}
int main() {
fast_io;
get_input();
memset(d, 63, sizeof(d));
dfs(e, 0);
memset(mark, 0, sizeof(mark)), memset(ans, 63, sizeof(ans));
main_dfs(e, 0);
while(q--) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
204888 KB |
Output is correct |
2 |
Correct |
80 ms |
204908 KB |
Output is correct |
3 |
Correct |
78 ms |
204936 KB |
Output is correct |
4 |
Correct |
82 ms |
204920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
204888 KB |
Output is correct |
2 |
Correct |
80 ms |
204908 KB |
Output is correct |
3 |
Correct |
78 ms |
204936 KB |
Output is correct |
4 |
Correct |
82 ms |
204920 KB |
Output is correct |
5 |
Correct |
81 ms |
205248 KB |
Output is correct |
6 |
Correct |
78 ms |
205160 KB |
Output is correct |
7 |
Correct |
75 ms |
205252 KB |
Output is correct |
8 |
Correct |
76 ms |
205220 KB |
Output is correct |
9 |
Correct |
77 ms |
205220 KB |
Output is correct |
10 |
Correct |
89 ms |
205180 KB |
Output is correct |
11 |
Correct |
78 ms |
205152 KB |
Output is correct |
12 |
Correct |
79 ms |
205200 KB |
Output is correct |
13 |
Correct |
75 ms |
205260 KB |
Output is correct |
14 |
Correct |
77 ms |
205236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
274 ms |
249344 KB |
Output is correct |
2 |
Correct |
259 ms |
248988 KB |
Output is correct |
3 |
Correct |
282 ms |
248984 KB |
Output is correct |
4 |
Correct |
334 ms |
250672 KB |
Output is correct |
5 |
Correct |
341 ms |
250796 KB |
Output is correct |
6 |
Correct |
379 ms |
252864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
204888 KB |
Output is correct |
2 |
Correct |
80 ms |
204908 KB |
Output is correct |
3 |
Correct |
78 ms |
204936 KB |
Output is correct |
4 |
Correct |
82 ms |
204920 KB |
Output is correct |
5 |
Correct |
81 ms |
205248 KB |
Output is correct |
6 |
Correct |
78 ms |
205160 KB |
Output is correct |
7 |
Correct |
75 ms |
205252 KB |
Output is correct |
8 |
Correct |
76 ms |
205220 KB |
Output is correct |
9 |
Correct |
77 ms |
205220 KB |
Output is correct |
10 |
Correct |
89 ms |
205180 KB |
Output is correct |
11 |
Correct |
78 ms |
205152 KB |
Output is correct |
12 |
Correct |
79 ms |
205200 KB |
Output is correct |
13 |
Correct |
75 ms |
205260 KB |
Output is correct |
14 |
Correct |
77 ms |
205236 KB |
Output is correct |
15 |
Correct |
274 ms |
249344 KB |
Output is correct |
16 |
Correct |
259 ms |
248988 KB |
Output is correct |
17 |
Correct |
282 ms |
248984 KB |
Output is correct |
18 |
Correct |
334 ms |
250672 KB |
Output is correct |
19 |
Correct |
341 ms |
250796 KB |
Output is correct |
20 |
Correct |
379 ms |
252864 KB |
Output is correct |
21 |
Correct |
224 ms |
248724 KB |
Output is correct |
22 |
Correct |
236 ms |
248496 KB |
Output is correct |
23 |
Correct |
280 ms |
248436 KB |
Output is correct |
24 |
Correct |
333 ms |
250296 KB |
Output is correct |
25 |
Correct |
384 ms |
253248 KB |
Output is correct |
26 |
Correct |
225 ms |
248820 KB |
Output is correct |
27 |
Correct |
279 ms |
248496 KB |
Output is correct |
28 |
Correct |
291 ms |
248444 KB |
Output is correct |
29 |
Correct |
350 ms |
249852 KB |
Output is correct |
30 |
Correct |
446 ms |
251252 KB |
Output is correct |
31 |
Correct |
217 ms |
249032 KB |
Output is correct |
32 |
Correct |
246 ms |
248584 KB |
Output is correct |
33 |
Correct |
281 ms |
248604 KB |
Output is correct |
34 |
Correct |
325 ms |
250332 KB |
Output is correct |
35 |
Correct |
373 ms |
253128 KB |
Output is correct |
36 |
Correct |
315 ms |
250636 KB |
Output is correct |