# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
753267 |
2023-06-04T23:50:13 Z |
beaboss |
Valley (BOI19_valley) |
C++14 |
|
435 ms |
67400 KB |
#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<ll> vi;
#define FOR(i, a, b) for (ll i = (a); i<b; i++)
const ll N = 1e5 + 10;
const ll MX = 20;
const ll INF = 1e17;
pii e[N];
vpii adj[N];
ll d[N];
ll anc[N][MX];
ll dist[N][MX];
ll dist2[N][MX];
bool shop[N];
ll subt_dist[N];
ll n, s, q, se;
ll jmp(ll x, ll d) {
if (d < 0) return x;
for (ll i = MX-1; i>= 0; i--) if ((1 << i) & (d)) x = anc[x][i];
return x;
}
ll best_shop(ll x, ll d) {
ll best = subt_dist[x];
ll acc = 0;
for (ll i = MX-1; i>= 0; i--) {
if ((1 << i) & (d)) {
best = min(best, acc + dist2[x][i]);
acc += dist[x][i];
x = anc[x][i];
// cout << x << endl;
}
}
return best;
}
int p[N];
void find_d(ll cur = se, ll pr = 0, ll w = 0) {
FOR(i, 0, MX) {
dist2[cur][i]=INF;
}
ll i = cur;
if (shop[cur]) {
subt_dist[i]=0;
}
else {
subt_dist[i] = INF;
}
// if (shop[pr]) {
// dist2[i][0] = w;
// }
// else {
// dist2[i][0]=INF;
// }
// cout << w << endl;
anc[cur][0]=pr;
dist[cur][0]=w;
for (auto val: adj[cur]) {
if (val.f != pr) {
d[val.f] = d[cur] + 1;
find_d(val.f, cur, val.s);
subt_dist[i] = min((ll) subt_dist[i], subt_dist[val.f]+val.s);
}
}
p[i]=pr;
dist2[i][0] = w;
}
int main() {
FOR(i, 0, MX) {
dist2[0][i]=INF;
}
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s >> q >> se;
ll w;
FOR(i, 0, n - 1) {
cin >> e[i].f >> e[i].s >> w;
adj[e[i].f].pb({e[i].s, w});
adj[e[i].s].pb({e[i].f, w});
}
FOR(i, 0, s) {
cin >> w;
shop[w]=true;
}
find_d();
FOR(i, 1, n + 1) {
dist2[i][0]+=subt_dist[p[i]];
}
FOR(j, 1, MX) FOR(i, 1, n + 1) anc[i][j] = anc[anc[i][j-1]][j-1];
FOR(j, 1, MX) FOR(i, 1, n + 1) dist[i][j] = dist[anc[i][j-1]][j-1] + dist[i][j-1];
// FOR(i, 1, n + 1) dist2[i][0] = subt_dist[p[i]];
FOR(j, 1, MX) FOR(i, 1, n + 1) dist2[i][j] = min(dist2[i][j-1], dist[i][j-1] + dist2[anc[i][j-1]][j-1]);
// cout << subt_dist[1] << endl;
// cout << dist2[2][0] << endl;
// cout << dist2[5][0] << endl;
FOR(i, 0, q) {
ll a, r;
cin >> a >> r;
a--;
ll v1, v2;
tie(v1, v2) = e[a];
if (d[v1] < d[v2]) swap(v1, v2);
if (jmp(r, d[r]-d[v1]) == v1) {
ll act = best_shop(r, d[r]-d[v1]);
if (act == INF) cout << "oo" << endl;
else cout << act << endl;
} else {
cout << "escaped" << endl;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
2900 KB |
Output is correct |
2 |
Correct |
16 ms |
2900 KB |
Output is correct |
3 |
Correct |
16 ms |
2900 KB |
Output is correct |
4 |
Correct |
18 ms |
2892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
2900 KB |
Output is correct |
2 |
Correct |
16 ms |
2900 KB |
Output is correct |
3 |
Correct |
16 ms |
2900 KB |
Output is correct |
4 |
Correct |
18 ms |
2892 KB |
Output is correct |
5 |
Correct |
4 ms |
3216 KB |
Output is correct |
6 |
Correct |
5 ms |
3212 KB |
Output is correct |
7 |
Correct |
4 ms |
3220 KB |
Output is correct |
8 |
Correct |
4 ms |
3284 KB |
Output is correct |
9 |
Correct |
5 ms |
3224 KB |
Output is correct |
10 |
Correct |
4 ms |
3284 KB |
Output is correct |
11 |
Correct |
4 ms |
3284 KB |
Output is correct |
12 |
Correct |
6 ms |
3284 KB |
Output is correct |
13 |
Correct |
6 ms |
3220 KB |
Output is correct |
14 |
Correct |
6 ms |
3284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
331 ms |
60372 KB |
Output is correct |
2 |
Correct |
351 ms |
61768 KB |
Output is correct |
3 |
Correct |
356 ms |
61848 KB |
Output is correct |
4 |
Correct |
402 ms |
63736 KB |
Output is correct |
5 |
Correct |
391 ms |
63820 KB |
Output is correct |
6 |
Correct |
404 ms |
66108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
2900 KB |
Output is correct |
2 |
Correct |
16 ms |
2900 KB |
Output is correct |
3 |
Correct |
16 ms |
2900 KB |
Output is correct |
4 |
Correct |
18 ms |
2892 KB |
Output is correct |
5 |
Correct |
4 ms |
3216 KB |
Output is correct |
6 |
Correct |
5 ms |
3212 KB |
Output is correct |
7 |
Correct |
4 ms |
3220 KB |
Output is correct |
8 |
Correct |
4 ms |
3284 KB |
Output is correct |
9 |
Correct |
5 ms |
3224 KB |
Output is correct |
10 |
Correct |
4 ms |
3284 KB |
Output is correct |
11 |
Correct |
4 ms |
3284 KB |
Output is correct |
12 |
Correct |
6 ms |
3284 KB |
Output is correct |
13 |
Correct |
6 ms |
3220 KB |
Output is correct |
14 |
Correct |
6 ms |
3284 KB |
Output is correct |
15 |
Correct |
331 ms |
60372 KB |
Output is correct |
16 |
Correct |
351 ms |
61768 KB |
Output is correct |
17 |
Correct |
356 ms |
61848 KB |
Output is correct |
18 |
Correct |
402 ms |
63736 KB |
Output is correct |
19 |
Correct |
391 ms |
63820 KB |
Output is correct |
20 |
Correct |
404 ms |
66108 KB |
Output is correct |
21 |
Correct |
326 ms |
62296 KB |
Output is correct |
22 |
Correct |
332 ms |
62084 KB |
Output is correct |
23 |
Correct |
373 ms |
62412 KB |
Output is correct |
24 |
Correct |
413 ms |
64384 KB |
Output is correct |
25 |
Correct |
391 ms |
67400 KB |
Output is correct |
26 |
Correct |
329 ms |
62352 KB |
Output is correct |
27 |
Correct |
345 ms |
62424 KB |
Output is correct |
28 |
Correct |
342 ms |
62344 KB |
Output is correct |
29 |
Correct |
366 ms |
64008 KB |
Output is correct |
30 |
Correct |
435 ms |
65576 KB |
Output is correct |
31 |
Correct |
328 ms |
62376 KB |
Output is correct |
32 |
Correct |
342 ms |
62348 KB |
Output is correct |
33 |
Correct |
369 ms |
62568 KB |
Output is correct |
34 |
Correct |
435 ms |
64476 KB |
Output is correct |
35 |
Correct |
392 ms |
67356 KB |
Output is correct |
36 |
Correct |
395 ms |
64332 KB |
Output is correct |