#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int>>> g, e;
vector<vector<int>> up;
vector<int> in, out, euler, id, f, dep;
vector<bool> c;
set<pair<int, int>> s1, s2;
int lg;
long long sum, s;
void dfs(int u) {
in[u] = euler.size();
euler.push_back(u);
for (int i = 1; i < lg; i++) up[i][u] = up[i - 1][up[i - 1][u]];
for (auto [v, i] : g[u])
if (v ^ up[0][u]) {
up[0][v] = u;
dep[v] = dep[u] + 1;
id[v] = i;
dfs(v);
}
out[u] = euler.size();
euler.push_back(u);
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
int k = dep[u] - dep[v];
for (int i = 0; i < lg; i++)
if (k >> i & 1)
u = up[i][u];
if (u == v) return u;
for (int i = lg - 1; i >= 0; i--)
if (up[i][u] ^ up[i][v])
u = up[i][u], v = up[i][v];
return up[0][u];
}
int block;
struct query {
int l, r, g, id;
long long s;
bool lca;
bool operator < (const query &q) const {
int a = l / block, b = q.l / block;
return a == b ? r < q.r : a < b;
}
};
void add(int i) {
for (auto [x, y] : e[i]) {
if (s1.size()) {
auto [mx, id] = *--s1.end();
if (x < mx) {
sum += x - mx;
s1.insert({x, y});
c[y] = 1;
if (sum + mx <= s) sum += mx;
else s1.erase(--s1.end()), s2.insert({mx, id}), c[id] = 0;
} else {
if (sum + x <= s) sum += x, c[y] = 1, s1.insert({x, y});
else s2.insert({x, y});
}
} else {
if (x <= s) sum = x, s1.insert({x, y}), c[y] = 1;
else s2.insert({x, y});
}
}
}
void remove(int i) {
for (auto [x, y] : e[i]) {
if (c[y]) {
sum -= x;
s1.erase({x, y});
c[y] = 0;
if (s2.size()) {
auto [x2, y2] = *s2.begin();
if (sum + x2 <= s) {
s2.erase({x2, y2});
s1.insert({x2, y2});
sum += x2;
}
}
} else s2.erase({x, y});
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
while ((1 << lg) <= n) ++lg;
block = sqrt(n), g.resize(n), up = vector<vector<int>> (lg, vector<int> (n)), id = dep = f = in = out = vector<int> (n), e.resize(n - 1), c.resize(m);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].emplace_back(v, i);
g[v].emplace_back(u, i);
}
for (int i = 0; i < m; i++) {
int p, c;
cin >> p >> c;
e[--p].push_back({c, i});
}
dfs(0);
vector<query> queries(q);
for (int i = 0; i < q; i++) {
int u, v, g;
long long s;
cin >> u >> v >> g >> s;
--u, --v;
if (in[u] > in[v]) swap(u, v);
int lc = lca(u, v);
if (u == lc) queries[i].l = in[u] + 1, queries[i].r = in[v];
else queries[i].l = out[u], queries[i].r = in[v];
queries[i].id = i, queries[i].g = g, queries[i].s = s;
}
vector<int> ans(q);
sort(queries.begin(), queries.end());
int l = queries[0].l, r = l - 1;
for (int i = 0; i < q; i++) {
int l_ = queries[i].l, r_ = queries[i].r;
s = queries[i].s;
while (sum > s) {
auto [x, y] = *--s1.end();
s1.erase({x, y});
s2.insert({x, y});
sum -= x;
c[y] = 0;
}
while (s2.size()) {
auto [x, y] = *s2.begin();
if (sum + x <= s) {
sum += x;
s1.insert({x, y});
s2.erase({x, y});
c[y] = 1;
} else break;
}
while (l > l_)
if (f[euler[l - 1]]++) remove(id[euler[--l]]);
else add(id[euler[--l]]);
while (r < r_)
if (f[euler[r + 1]]++) remove(id[euler[++r]]);
else add(id[euler[++r]]);
while (l < l_)
if (--f[euler[l]]) add(id[euler[l++]]);
else remove(id[euler[l++]]);
while (r > r_)
if (--f[euler[r]]) add(id[euler[r--]]);
else remove(id[euler[r--]]);
ans[queries[i].id] = s2.size() > queries[i].g ? -1 : s2.size();
}
for (int v : ans) cout << v << '\n';
}
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:157:40: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
157 | ans[queries[i].id] = s2.size() > queries[i].g ? -1 : s2.size();
| ~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
