# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
856933 |
2023-10-04T22:48:07 Z |
rxlfd314 |
Valley (BOI19_valley) |
C++17 |
|
864 ms |
176292 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
#define chmax(a, b) a = a > (b) ? a : (b)
#define chmin(a, b) a = a < (b) ? a : (b)
constexpr int mxN = 100000;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
int N, S, Q, E, edges[mxN][2];
vt<ari2> adj[mxN];
int tin[mxN], tout[mxN], timer, lift[mxN][17];
ll depth[mxN];
bool shop[mxN];
void dfs(int i, int p) {
tin[i] = timer++;
for (auto [j, v] : adj[i]) {
if (j == p)
continue;
depth[j] = depth[i] + v;
dfs(j, i);
}
tout[i] = timer - 1;
lift[i][0] = p;
}
bool ia(int a, int b) {
return tin[a] <= tin[b] && tin[b] <= tout[a];
}
int LCA(int a, int b) {
if (ia(a, b))
return a;
if (ia(b, a))
return b;
ROF(i, 16, 0)
a = ia(lift[a][i], b) ? a : lift[a][i];
return lift[a][0];
}
ll dist(int a, int b) {
return depth[a] + depth[b] - 2 * depth[LCA(a, b)];
}
int szs[mxN];
bool dead[mxN];
int gs(int i, int p) {
szs[i] = 1;
for (auto [j, _] : adj[i])
if (!dead[j] && j != p)
szs[i] += gs(j, i);
return szs[i];
}
int fc(int i, int n) {
int p = i;
bool flag = true;
while (flag) {
flag = false;
for (auto [j, _] : adj[i])
if (!dead[j] && j != p && szs[j] > n >> 1) {
p = i;
i = j;
flag = true;
break;
}
}
return i;
}
int pr[mxN];
void cd_init(int i, int p) {
int c = fc(i, gs(i, i));
pr[c] = p;
dead[c] = true;
for (auto [j, _] : adj[c])
if (!dead[j])
cd_init(j, c);
}
struct Node {
ll val = INF;
Node *lft = nullptr, *rht = nullptr;
void upd(int p, ll v, int tl, int tr) {
if (tl == tr)
chmin(val, v);
else {
int tm = tl + tr >> 1;
if (p > tm) {
if (!rht)
rht = new Node;
rht->upd(p, v, tm+1, tr);
} else {
if (!lft)
lft = new Node;
lft->upd(p, v, tl, tm);
}
val = min(lft ? lft->val : INF, rht ? rht->val : INF);
}
}
ll qry(int ql, int qr, int tl, int tr) {
if (tl > qr || tr < ql)
return INF;
if (ql <= tl && tr <= qr)
return val;
int tm = tl + tr >> 1;
return min(lft ? lft->qry(ql, qr, tl, tm) : INF, rht ? rht->qry(ql, qr, tm+1, tr) : INF);
}
} sts[mxN];
void init() {
dfs(0, 0);
FOR(j, 1, 16)
FOR(i, 0, N-1)
lift[i][j] = lift[lift[i][j-1]][j-1];
cd_init(0, -1);
FOR(i, 0, N-1)
if (shop[i])
for (int j = i; ~j; j = pr[j])
sts[j].upd(tin[i], dist(i, j), 0, N-1);
}
signed main() {
#ifndef DEBUG
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#endif
cin >> N >> S >> Q >> E, E--;
FOR(i, 1, N-1) {
int &a = edges[i][0], &b = edges[i][1], c;
cin >> a >> b >> c;
adj[--a].push_back({--b, c});
adj[b].push_back({a, c});
}
FOR(_, 1, S) {
int v;
cin >> v;
shop[--v] = true;
}
init();
while (Q--) {
int x, y;
cin >> x >> y, y--;
int a = edges[x][0], b = edges[x][1];
if (ia(b, a))
swap(a, b);
bool in_sub = ia(b, y);
if (ia(b, E) && in_sub || !ia(b, E) && !in_sub) {
cout << "escaped\n";
continue;
}
ll ans = INF;
for (int j = y; ~j; j = pr[j]) {
if (in_sub ^ ia(b, j))
continue;
ll d = dist(j, y);
if (in_sub)
ans = min(ans, sts[j].qry(tin[b], tout[b], 0, N-1) + dist(j, y));
else
ans = min({ans - d, sts[j].qry(0, tin[b]-1, 0, N-1), sts[j].qry(tout[b]+1, N-1, 0, N-1)}) + d;
}
if (ans < INF)
cout << ans;
else
cout << "oo";
cout << '\n';
}
}
Compilation message
valley.cpp: In member function 'void Node::upd(int, ll, int, int)':
valley.cpp:98:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
98 | int tm = tl + tr >> 1;
| ~~~^~~~
valley.cpp: In member function 'll Node::qry(int, int, int, int)':
valley.cpp:116:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
116 | int tm = tl + tr >> 1;
| ~~~^~~~
valley.cpp: In function 'int main()':
valley.cpp:160:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
160 | if (ia(b, E) && in_sub || !ia(b, E) && !in_sub) {
| ~~~~~~~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4696 KB |
Output is correct |
2 |
Correct |
3 ms |
4696 KB |
Output is correct |
3 |
Correct |
3 ms |
4700 KB |
Output is correct |
4 |
Correct |
3 ms |
4700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4696 KB |
Output is correct |
2 |
Correct |
3 ms |
4696 KB |
Output is correct |
3 |
Correct |
3 ms |
4700 KB |
Output is correct |
4 |
Correct |
3 ms |
4700 KB |
Output is correct |
5 |
Correct |
1 ms |
4700 KB |
Output is correct |
6 |
Correct |
2 ms |
4548 KB |
Output is correct |
7 |
Correct |
2 ms |
4700 KB |
Output is correct |
8 |
Correct |
2 ms |
4696 KB |
Output is correct |
9 |
Correct |
2 ms |
4700 KB |
Output is correct |
10 |
Correct |
2 ms |
4700 KB |
Output is correct |
11 |
Correct |
2 ms |
5208 KB |
Output is correct |
12 |
Correct |
3 ms |
5316 KB |
Output is correct |
13 |
Correct |
3 ms |
5464 KB |
Output is correct |
14 |
Correct |
2 ms |
4956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
337 ms |
101188 KB |
Output is correct |
2 |
Correct |
540 ms |
126228 KB |
Output is correct |
3 |
Correct |
779 ms |
144180 KB |
Output is correct |
4 |
Correct |
864 ms |
164944 KB |
Output is correct |
5 |
Correct |
747 ms |
164512 KB |
Output is correct |
6 |
Correct |
849 ms |
176292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4696 KB |
Output is correct |
2 |
Correct |
3 ms |
4696 KB |
Output is correct |
3 |
Correct |
3 ms |
4700 KB |
Output is correct |
4 |
Correct |
3 ms |
4700 KB |
Output is correct |
5 |
Correct |
1 ms |
4700 KB |
Output is correct |
6 |
Correct |
2 ms |
4548 KB |
Output is correct |
7 |
Correct |
2 ms |
4700 KB |
Output is correct |
8 |
Correct |
2 ms |
4696 KB |
Output is correct |
9 |
Correct |
2 ms |
4700 KB |
Output is correct |
10 |
Correct |
2 ms |
4700 KB |
Output is correct |
11 |
Correct |
2 ms |
5208 KB |
Output is correct |
12 |
Correct |
3 ms |
5316 KB |
Output is correct |
13 |
Correct |
3 ms |
5464 KB |
Output is correct |
14 |
Correct |
2 ms |
4956 KB |
Output is correct |
15 |
Correct |
337 ms |
101188 KB |
Output is correct |
16 |
Correct |
540 ms |
126228 KB |
Output is correct |
17 |
Correct |
779 ms |
144180 KB |
Output is correct |
18 |
Correct |
864 ms |
164944 KB |
Output is correct |
19 |
Correct |
747 ms |
164512 KB |
Output is correct |
20 |
Correct |
849 ms |
176292 KB |
Output is correct |
21 |
Correct |
80 ms |
20584 KB |
Output is correct |
22 |
Correct |
95 ms |
20060 KB |
Output is correct |
23 |
Correct |
106 ms |
20188 KB |
Output is correct |
24 |
Correct |
127 ms |
21540 KB |
Output is correct |
25 |
Correct |
163 ms |
23928 KB |
Output is correct |
26 |
Correct |
68 ms |
21840 KB |
Output is correct |
27 |
Correct |
90 ms |
22096 KB |
Output is correct |
28 |
Correct |
102 ms |
22352 KB |
Output is correct |
29 |
Correct |
161 ms |
23900 KB |
Output is correct |
30 |
Correct |
147 ms |
25508 KB |
Output is correct |
31 |
Correct |
94 ms |
36012 KB |
Output is correct |
32 |
Correct |
158 ms |
44744 KB |
Output is correct |
33 |
Correct |
182 ms |
49232 KB |
Output is correct |
34 |
Correct |
267 ms |
55316 KB |
Output is correct |
35 |
Correct |
216 ms |
59360 KB |
Output is correct |
36 |
Correct |
285 ms |
84488 KB |
Output is correct |