QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#178657 | #6332. Two Currencies | rgnerdplayer | 0 | 119ms | 20036kb | C++20 | 5.7kb | 2023-09-14 10:40:58 | 2023-09-14 10:40:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct HLD {
int n, cur = 0;
vector<int> sz, top, dep, par, tin, tout, seq;
vector<vector<int>> adj;
HLD(int n) : n(n), sz(n, 1), top(n), dep(n), par(n), tin(n), tout(n), seq(n), adj(n) {}
void addEdge(int u, int v) { adj[u].push_back(v), adj[v].push_back(u); }
void build(int root = 0) {
top[root] = root, dep[root] = 0, par[root] = -1;
dfs1(root), dfs2(root);
}
void dfs1(int u) {
if (auto it = find(adj[u].begin(), adj[u].end(), par[u]); it != adj[u].end()) {
adj[u].erase(it);
}
for (auto &v : adj[u]) {
par[v] = u;
dep[v] = dep[u] + 1;
dfs1(v);
sz[u] += sz[v];
if (sz[v] > sz[adj[u][0]]) { swap(v, adj[u][0]); }
}
}
void dfs2(int u) {
tin[u] = cur++;
seq[tin[u]] = u;
for (auto v : adj[u]) {
top[v] = v == adj[u][0] ? top[u] : v;
dfs2(v);
}
tout[u] = cur - 1;
}
int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) {
u = par[top[u]];
} else {
v = par[top[v]];
}
}
return dep[u] < dep[v] ? u : v;
}
int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
int jump(int u, int k) {
if (dep[u] < k) { return -1; }
int d = dep[u] - k;
while (dep[top[u]] > d) { u = par[top[u]]; }
return seq[tin[u] - dep[u] + d];
}
// u is v's ancestor
bool isAncestor(int u, int v) { return tin[u] <= tin[v] && tin[v] <= tout[u]; }
// root's parent is itself
int rootedParent(int r, int u) {
if (r == u) { return u; }
if (isAncestor(r, u)) { return par[u]; }
auto it = upper_bound(adj[u].begin(), adj[u].end(), r, [&](int x, int y) {
return tin[x] < tin[y];
}) - 1;
return *it;
}
// rooted at u, v's subtree size
int rootedSize(int r, int u) {
if (r == u) { return n; }
if (isAncestor(u, r)) { return sz[u]; }
return n - sz[rootedParent(r, u)];
}
int rootedLca(int r, int a, int b) { return lca(a, b) ^ lca(a, r) ^ lca(b, r); }
};
template <typename T>
struct Fenwick {
int n;
vector<T> a;
Fenwick(int n = 0) : n(n), a(n) {}
void add(int p, T v) {
while (p < n) {
a[p] += v;
p |= p + 1;
}
}
T sum(int p) {
T res = {};
while (p >= 0) {
res += a[p];
p = (p & p + 1) - 1;
}
return res;
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
auto solve = [&]() {
int n, m, q;
cin >> n >> m >> q;
vector<array<int, 2>> e(n - 1);
HLD g(n);
for (auto &[u, v] : e) {
cin >> u >> v;
u--, v--;
g.addEdge(u, v);
}
g.build();
for (auto &[u, v] : e) {
if (g.dep[u] < g.dep[v]) {
swap(u, v);
}
}
vector<array<int, 2>> points(m);
for (auto &[c, u] : points) {
cin >> u >> c;
u--;
u = e[u][0];
}
sort(points.begin(), points.end());
vector<array<int, 4>> qs(q);
for (auto &[s, t, x, y] : qs) {
cin >> s >> t >> x >> y;
s--, t--;
}
vector<int> low(q), high(q, m);
auto dist = [&](int u, int v, auto &f) {
return f.sum(g.tin[u]) + f.sum(g.tin[v]) - 2 * f.sum(g.tin[g.lca(u, v)]);
};
while (true) {
bool done = true;
vector<array<int, 2>> ord;
for (int i = 0; i < q; i++) {
if (low[i] < high[i]) {
done = false;
int mid = (low[i] + high[i] + 1) / 2;
ord.push_back({mid, i});
}
}
if (done) {
break;
}
sort(ord.begin(), ord.end());
Fenwick<i64> f(n);
for (int j = 0; auto [mid, i] : ord) {
while (j < mid) {
auto [c, u] = points[j];
f.add(g.tin[u], c);
f.add(g.tout[u] + 1, -c);
j++;
}
auto [s, t, x, y] = qs[i];
if (dist(s, t, f) <= y) {
low[i] = mid;
} else {
high[i] = mid - 1;
}
}
}
vector<int> ord(q);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](auto i, auto j) { return low[i] < low[j]; });
vector<int> ans(q);
Fenwick<int> f(n);
int j = 0;
for (auto i : ord) {
while (j < low[i]) {
auto [c, u] = points[j];
f.add(g.tin[u], 1);
f.add(g.tout[u] + 1, -1);
j++;
}
auto [s, t, x, y] = qs[i];
ans[i] -= dist(s, t, f);
}
while (j < m) {
auto [c, u] = points[j];
f.add(g.tin[u], 1);
f.add(g.tout[u] + 1, -1);
j++;
}
for (int i = 0; i < q; i++) {
auto [s, t, x, y] = qs[i];
ans[i] += dist(s, t, f);
ans[i] = max(-1, x - ans[i]);
}
for (int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
};
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3708kb
input:
1831 1865 1153 832 1698 1672 1619 634 920 328 1244 571 1279 1673 1815 1098 92 1320 432 244 636 991 1446 308 569 1118 1356 1733 71 497 1679 1699 635 1254 1295 853 345 364 1396 1183 1134 524 1557 1642 1262 1767 459 918 794 1644 539 902 1046 334 1789 1691 1548 1298 520 1763 216 1161 1065 682 1167 1282 ...
output:
378730601 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '378730605', found: '378730601'
Subtask #2:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 119ms
memory: 16196kb
input:
99819 89735 60985 59741 24953 61387 12293 53761 1828 60970 60534 40598 48807 21876 21232 29527 13335 84269 40756 89571 12996 25757 40587 52477 63347 41372 69243 16391 58678 40854 39513 84384 91744 62938 60371 81932 45504 34121 54746 51945 14294 883 85344 78845 51797 45025 76590 37694 65493 4118 2588...
output:
25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
wrong answer 1st numbers differ - expected: '36', found: '25'
Subtask #3:
score: 0
Wrong Answer
Test #59:
score: 0
Wrong Answer
time: 88ms
memory: 20036kb
input:
95629 64841 64314 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51...
output:
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
wrong answer 2nd numbers differ - expected: '701714740', found: '0'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%