#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#else
#define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
// #define int long long
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
END OF TEMPLATE
----------------------------------------------------------------
Tran The Bao - ghostwriter
Training for VOI23 gold medal
----------------------------------------------------------------
DIT ME TTB NON
----------------------------------------------------------------
*/
#define matrix vector<vi>
#define matrix1 vector<vpi>
const ll oo = (ll)1e18 + 5;
const int N = 1e5 + 1;
const int Nx2 = 2e5 + 1;
int n, s, q, e, p1[N][17], p[N], tin[N], tout[N], s1[N], c[N], query[N], timer = 0, root = 0;
ll h1[N], h2[N], h[N], f[Nx2], ans[N];
matrix pre[N], suf[N];
matrix1 seg[N];
vpi edge, adj[N];
vi a[N], a1[N], adj1[N];
void upd(int pos, ll v) { for (int i = pos; i >= 1; i -= (i & -i)) f[i] = min(f[i], v); }
ll get(int pos) { ll rs = oo; for (int i = pos; i <= 2 * n; i += (i & -i)) rs = min(rs, f[i]); return rs; }
void upd1(int pos) { for (int i = pos; i >= 1; i -= (i & -i)) f[i] = oo; }
void dfs(int u, int p) {
p1[u][0] = p;
tin[u] = ++timer;
EACH(j, adj[u]) {
int v = j.st, w = j.nd;
if (v == p) continue;
h1[v] = h1[u] + w;
h2[v] = h2[u] + 1;
dfs(v, u);
}
tout[u] = ++timer;
}
void build() {
FOR(j, 1, 16)
FOR(i, 1, n)
p1[i][j] = p1[p1[i][j - 1]][j - 1];
}
int lca(int a, int b) {
if (h2[a] > h2[b]) swap(a, b);
int diff = h2[b] - h2[a];
FOR(i, 0, 16)
if (diff & (1 << i))
b = p1[b][i];
if (a == b) return a;
FOS(i, 16, 0)
if (p1[a][i] != p1[b][i]) {
a = p1[a][i];
b = p1[b][i];
}
return p1[a][0];
}
ll dis(int a, int b) { return h1[a] + h1[b] - 2LL * h1[lca(a, b)]; }
bool isc(int a, int b) { return tin[a] >= tin[b] && tout[b] >= tout[a]; }
int getp(pi a) {
if (isc(a.st, a.nd)) return a.st;
return a.nd;
}
void dfs1(int u, int p) {
s1[u] = 1;
EACH(j, adj[u]) {
int v = j.st;
if (c[v] || v == p) continue;
dfs1(v, u);
s1[u] += s1[v];
}
}
int fct(int u, int p, int total) {
EACH(j, adj[u]) {
int v = j.st;
if (c[v] || v == p) continue;
if (s1[v] > total / 2) return fct(v, u, total);
}
return u;
}
void merge(vi &a, vi &b) { // by tin
int l = 0;
vi ans;
EACH(i, a) {
WHILE(l < sz(b) && tin[b[l]] < tin[i]) ans.pb(b[l++]);
ans.pb(i);
}
WHILE(l < sz(b)) ans.pb(b[l++]);
a = ans;
}
void merge1(vi &a, vi &b) { // by tout
int l = 0;
vi ans;
EACH(i, a) {
WHILE(l < sz(b) && tout[b[l]] < tout[i]) ans.pb(b[l++]);
ans.pb(i);
}
WHILE(l < sz(b)) ans.pb(b[l++]);
a = ans;
}
int centroid(int u) {
dfs1(u, 0);
int ct = fct(u, 0, s1[u]);
c[ct] = 1;
a[ct].pb(ct);
a1[ct].pb(ct);
h[ct] = 0;
EACH(j, adj[ct]) {
int v = j.st;
if (c[v]) continue;
int nxt = centroid(v);
p[nxt] = ct;
vi &an = a[nxt], &a1n = a1[nxt];
merge(a[ct], an);
merge1(a1[ct], a1n);
adj1[ct].pb(nxt);
}
int m = sz(a[ct]);
pre[ct].resize(m);
suf[ct].resize(m);
seg[ct].resize(m);
return ct;
}
void add(int i, int R, int u, int id) {
int m = sz(a[u]);
int l = 0, r = m - 1, ans1 = -1, ans2 = -1, ans3 = -1;
WHILE(l <= r) {
int mid = l + (r - l) / 2;
if (tin[a[u][mid]] < tin[i]) {
ans1 = mid;
l = mid + 1;
}
else r = mid - 1;
}
l = 0; r = m - 1;
WHILE(l <= r) {
int mid = l + (r - l) / 2;
if (tout[a1[u][mid]] > tout[i]) {
ans2 = mid;
r = mid - 1;
}
else l = mid + 1;
}
l = 0; r = m - 1;
WHILE(l <= r) {
int mid = l + (r - l) / 2;
if (tout[a1[u][mid]] <= tout[i]) {
ans3 = mid;
l = mid + 1;
}
else r = mid - 1;
}
if (isc(R, i)) {
if (ans3 != -1) seg[u][ans3].pb({id, tin[i]});
}
else {
if (ans1 != -1) pre[u][ans1].pb(id);
if (ans2 != -1) suf[u][ans2].pb(id);
}
if (p[u]) add(i, R, p[u], id);
}
void process(int u) {
int m = sz(a[u]);
ll Min = oo;
FOS(i, m - 1, 0) {
int cur = a1[u][i];
if (cur == e) Min = min(Min, -oo);
else if (c[cur]) Min = min(Min, dis(u, cur));
EACH(v, suf[u][i]) ans[v] = min(ans[v], dis(u, query[v]) + Min);
}
Min = oo;
FOR(i, 0, m - 1) {
int cur = a[u][i];
if (cur == e) Min = min(Min, -oo);
else if (c[cur]) Min = min(Min, dis(u, cur));
EACH(v, pre[u][i]) ans[v] = min(ans[v], dis(u, query[v]) + Min);
}
FOR(i, 0, m - 1) {
int cur = a1[u][i];
if (cur == e) upd(tin[cur], -oo);
else if (c[cur]) upd(tin[cur], dis(u, cur));
EACH(j, seg[u][i]) {
int v = j.st, t = j.nd;
ans[v] = min(ans[v], dis(u, query[v]) + get(t));
}
}
FOR(i, 0, m - 1) {
int cur = a1[u][i];
upd1(tin[cur]);
}
EACH(v, adj1[u]) process(v);
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
cin >> n >> s >> q >> e;
FOR(i, 1, 2 * n) f[i] = oo;
edge.pb({0, 0});
FOR(i, 1, n - 1) {
int u, v, w;
cin >> u >> v >> w;
edge.pb({u, v});
adj[u].pb({v, w});
adj[v].pb({u, w});
}
dfs(1, 0);
build();
root = centroid(1);
memset(c, 0, sizeof c);
FOR(i, 1, s) {
int ci;
cin >> ci;
c[ci] = 1;
}
FOR(j, 1, q) {
ans[j] = oo;
int i, r;
cin >> i >> r;
add(getp(edge[i]), r, r, j);
query[j] = r;
}
process(root);
FOR(i, 1, q)
if (ans[i] < 0) cout << "escaped\n";
else if (ans[i] < oo) cout << ans[i] << '\n';
else cout << "oo\n";
return 0;
}
/*
5 2 3 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
2 2
2 5
4 5
----------------------------------------------------------------
From Benq:
stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/
Compilation message
valley.cpp: In function 'void dfs(int, int)':
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:69:2: note: in expansion of macro 'EACH'
69 | EACH(j, adj[u]) {
| ^~~~
valley.cpp: In function 'void build()':
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:79:2: note: in expansion of macro 'FOR'
79 | FOR(j, 1, 16)
| ^~~
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:80:2: note: in expansion of macro 'FOR'
80 | FOR(i, 1, n)
| ^~~
valley.cpp: In function 'int lca(int, int)':
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:86:2: note: in expansion of macro 'FOR'
86 | FOR(i, 0, 16)
| ^~~
valley.cpp:34:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
34 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
| ^
valley.cpp:90:2: note: in expansion of macro 'FOS'
90 | FOS(i, 16, 0)
| ^~~
valley.cpp: In function 'void dfs1(int, int)':
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:105:2: note: in expansion of macro 'EACH'
105 | EACH(j, adj[u]) {
| ^~~~
valley.cpp: In function 'int fct(int, int, int)':
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:113:2: note: in expansion of macro 'EACH'
113 | EACH(j, adj[u]) {
| ^~~~
valley.cpp: In function 'void merge(vi&, vi&)':
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:123:2: note: in expansion of macro 'EACH'
123 | EACH(i, a) {
| ^~~~
valley.cpp: In function 'void merge1(vi&, vi&)':
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:133:2: note: in expansion of macro 'EACH'
133 | EACH(i, a) {
| ^~~~
valley.cpp: In function 'int centroid(int)':
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:147:2: note: in expansion of macro 'EACH'
147 | EACH(j, adj[ct]) {
| ^~~~
valley.cpp: In function 'void process(int)':
valley.cpp:34:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
34 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
| ^
valley.cpp:204:2: note: in expansion of macro 'FOS'
204 | FOS(i, m - 1, 0) {
| ^~~
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:208:3: note: in expansion of macro 'EACH'
208 | EACH(v, suf[u][i]) ans[v] = min(ans[v], dis(u, query[v]) + Min);
| ^~~~
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:211:2: note: in expansion of macro 'FOR'
211 | FOR(i, 0, m - 1) {
| ^~~
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:215:3: note: in expansion of macro 'EACH'
215 | EACH(v, pre[u][i]) ans[v] = min(ans[v], dis(u, query[v]) + Min);
| ^~~~
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:217:2: note: in expansion of macro 'FOR'
217 | FOR(i, 0, m - 1) {
| ^~~
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:221:3: note: in expansion of macro 'EACH'
221 | EACH(j, seg[u][i]) {
| ^~~~
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:226:2: note: in expansion of macro 'FOR'
226 | FOR(i, 0, m - 1) {
| ^~~
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:230:2: note: in expansion of macro 'EACH'
230 | EACH(v, adj1[u]) process(v);
| ^~~~
valley.cpp: In function 'int main()':
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:237:5: note: in expansion of macro 'FOR'
237 | FOR(i, 1, 2 * n) f[i] = oo;
| ^~~
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:239:5: note: in expansion of macro 'FOR'
239 | FOR(i, 1, n - 1) {
| ^~~
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:250:5: note: in expansion of macro 'FOR'
250 | FOR(i, 1, s) {
| ^~~
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:255:5: note: in expansion of macro 'FOR'
255 | FOR(j, 1, q) {
| ^~~
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:263:5: note: in expansion of macro 'FOR'
263 | FOR(i, 1, q)
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
18132 KB |
Output is correct |
| 2 |
Correct |
18 ms |
18132 KB |
Output is correct |
| 3 |
Correct |
18 ms |
18132 KB |
Output is correct |
| 4 |
Correct |
19 ms |
18120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
18132 KB |
Output is correct |
| 2 |
Correct |
18 ms |
18132 KB |
Output is correct |
| 3 |
Correct |
18 ms |
18132 KB |
Output is correct |
| 4 |
Correct |
19 ms |
18120 KB |
Output is correct |
| 5 |
Correct |
12 ms |
17876 KB |
Output is correct |
| 6 |
Correct |
12 ms |
18104 KB |
Output is correct |
| 7 |
Correct |
12 ms |
18132 KB |
Output is correct |
| 8 |
Correct |
15 ms |
17800 KB |
Output is correct |
| 9 |
Correct |
16 ms |
18048 KB |
Output is correct |
| 10 |
Correct |
13 ms |
18096 KB |
Output is correct |
| 11 |
Correct |
12 ms |
17876 KB |
Output is correct |
| 12 |
Correct |
15 ms |
18188 KB |
Output is correct |
| 13 |
Correct |
14 ms |
18092 KB |
Output is correct |
| 14 |
Correct |
14 ms |
18100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1022 ms |
95808 KB |
Output is correct |
| 2 |
Correct |
1431 ms |
133996 KB |
Output is correct |
| 3 |
Correct |
1911 ms |
158964 KB |
Output is correct |
| 4 |
Correct |
2335 ms |
190424 KB |
Output is correct |
| 5 |
Correct |
1332 ms |
172080 KB |
Output is correct |
| 6 |
Correct |
1386 ms |
191120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
18132 KB |
Output is correct |
| 2 |
Correct |
18 ms |
18132 KB |
Output is correct |
| 3 |
Correct |
18 ms |
18132 KB |
Output is correct |
| 4 |
Correct |
19 ms |
18120 KB |
Output is correct |
| 5 |
Correct |
12 ms |
17876 KB |
Output is correct |
| 6 |
Correct |
12 ms |
18104 KB |
Output is correct |
| 7 |
Correct |
12 ms |
18132 KB |
Output is correct |
| 8 |
Correct |
15 ms |
17800 KB |
Output is correct |
| 9 |
Correct |
16 ms |
18048 KB |
Output is correct |
| 10 |
Correct |
13 ms |
18096 KB |
Output is correct |
| 11 |
Correct |
12 ms |
17876 KB |
Output is correct |
| 12 |
Correct |
15 ms |
18188 KB |
Output is correct |
| 13 |
Correct |
14 ms |
18092 KB |
Output is correct |
| 14 |
Correct |
14 ms |
18100 KB |
Output is correct |
| 15 |
Correct |
1022 ms |
95808 KB |
Output is correct |
| 16 |
Correct |
1431 ms |
133996 KB |
Output is correct |
| 17 |
Correct |
1911 ms |
158964 KB |
Output is correct |
| 18 |
Correct |
2335 ms |
190424 KB |
Output is correct |
| 19 |
Correct |
1332 ms |
172080 KB |
Output is correct |
| 20 |
Correct |
1386 ms |
191120 KB |
Output is correct |
| 21 |
Correct |
946 ms |
98948 KB |
Output is correct |
| 22 |
Correct |
1293 ms |
139896 KB |
Output is correct |
| 23 |
Correct |
1603 ms |
163504 KB |
Output is correct |
| 24 |
Correct |
1978 ms |
189140 KB |
Output is correct |
| 25 |
Correct |
1071 ms |
184388 KB |
Output is correct |
| 26 |
Correct |
952 ms |
99732 KB |
Output is correct |
| 27 |
Correct |
1306 ms |
137880 KB |
Output is correct |
| 28 |
Correct |
1624 ms |
166976 KB |
Output is correct |
| 29 |
Correct |
1867 ms |
188604 KB |
Output is correct |
| 30 |
Correct |
1202 ms |
182344 KB |
Output is correct |
| 31 |
Correct |
909 ms |
98212 KB |
Output is correct |
| 32 |
Correct |
1409 ms |
141452 KB |
Output is correct |
| 33 |
Correct |
1658 ms |
163452 KB |
Output is correct |
| 34 |
Correct |
1995 ms |
188348 KB |
Output is correct |
| 35 |
Correct |
1085 ms |
180352 KB |
Output is correct |
| 36 |
Correct |
1188 ms |
156204 KB |
Output is correct |
