이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int inff = 1e18;
const int lim = 1e14;
struct node {
int val, lz;
int st, en;
node *left, *right;
void build(int start, int end, vector<int> &a) {
st = start;
en = end;
lz = 0;
if (st == en) {
val = a[st];
return;
}
int md = (st + en) / 2;
left = new node();
right = new node();
left->build(st, md, a);
right->build(md + 1, en, a);
val = min(left->val, right->val);
}
void lazy() {
left->val += lz;
left->lz += lz;
right->val += lz;
right->lz += lz;
lz = 0;
}
int query(int lf, int rg) {
if (st > rg || en < lf) return inff;
if (lf <= st && en <= rg) return val;
lazy();
return min(left->query(lf, rg), right->query(lf, rg));
}
void update(int lf, int rg, int x) {
if (st > rg || en < lf) return;
if (lf <= st && en <= rg) {
val += x;
lz += x;
return;
}
lazy();
left->update(lf, rg, x);
right->update(lf, rg, x);
val = min(left->val, right->val);
}
} sg;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, s, q, e;
cin >> n >> s >> q >> e;
vector<int> a(n), b(n), c(n);
vector<vector<pair<int, int>>> v(n + 1);
for (int i = 1; i <= n - 1; i++) {
cin >> a[i] >> b[i] >> c[i];
v[a[i]].push_back({b[i], c[i]});
v[b[i]].push_back({a[i], c[i]});
}
vector<int> ok(n + 1);
for (int i = 1; i <= s; i++) {
int x;
cin >> x;
ok[x] = 1;
}
vector<vector<pair<int, int>>> qr(n + 1);
for (int i = 0; i < q; i++) {
int j, x;
cin >> j >> x;
qr[x].push_back({j, i});
}
int tim = 0;
vector<int> dep(n + 1), d(n + 1), tin(n + 1), tout(n + 1);
function<void(int, int)> dfs = [&](int x, int p) {
tin[x] = ++tim;
for (auto [z, c] : v[x]) {
if (z == p) continue;
dep[z] = dep[x] + 1;
d[z] = d[x] + c;
dfs(z, x);
}
tout[x] = tim;
};
dfs(1, 1);
vector<int> ans(q), val(n + 1, inff);
for (int i = 1; i <= n; i++) {
if (ok[i]) {
val[tin[i]] = d[i];
}
}
sg.build(1, n, val);
auto upper = [&](int x, int y) {
return tin[x] <= tin[y] && tout[y] <= tout[y];
};
function<void(int, int)> dfs2 = [&](int x, int p) {
for (auto [j, i] : qr[x]) {
if (dep[a[j]] < dep[b[j]]) swap(a[j], b[j]);
if (upper(a[j], x)) {
if (upper(a[j], e)) {
ans[i] = -1;
} else {
ans[i] = sg.query(tin[a[j]], tout[a[j]]);
}
} else {
if (!upper(a[j], e)) {
ans[i] = -1;
} else {
ans[i] = min(sg.query(1, tin[a[j]] - 1), sg.query(tout[a[j]] + 1, n));
}
}
}
for (auto [z, c] : v[x]) {
if (z == p) continue;
sg.update(1, n, c);
sg.update(tin[z], tout[z], -2 * c);
dfs2(z, x);
sg.update(1, n, -c);
sg.update(tin[z], tout[z], 2 * c);
}
};
dfs2(1, 1);
for (int i = 0; i < q; i++) {
if (ans[i] == -1) {
cout << "escaped" << '\n';
} else if (ans[i] <= lim) {
cout << ans[i] << '\n';
} else {
cout << "oo" << '\n';
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |