#include <bits/stdc++.h>
using namespace std;
int64_t f[100000], af[100000];
void update(int p, int x) {
while (p < 100000) {
f[p] += x;
p |= p + 1;
}
}
int64_t query(int p) {
int res = 0;
while (p >= 0) {
res += f[p];
p = (p & (p + 1)) - 1;
}
return res;
}
void update(int p, int x, int y) {
while (p < 100000) {
f[p] += x;
af[p] += y;
p |= p + 1;
}
}
pair<int64_t, int> duo_query(int p) {
pair<int64_t, int> res{0, 0};
while (p >= 0) {
res.first += f[p];
res.second += af[p];
p = (p & (p + 1)) - 1;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<int> ce(n - 1);
vector<vector<int>> adj(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u -= 1;
v -= 1;
adj[u].emplace_back(i);
adj[v].emplace_back(i);
ce[i] = u ^ v;
}
vector<int> cv;
vector<pair<int, int>> cp(m);
for (int i = 0; i < m; i++) {
int u, x;
cin >> u >> x;
u -= 1;
cp[i] = make_pair(u, x);
cv.emplace_back(x);
}
sort(cv.begin(), cv.end());
cv.erase(unique(cv.begin(), cv.end()), cv.end());
vector<int> dfn(n), size(n), top(n), depth(n), parent(n), c(n - 1);
{
function<void(int)> dfs = [&](int u) -> void {
size[u] = 1;
for (int &i : adj[u]) {
int v = ce[i] ^ u;
adj[v].erase(find(adj[v].begin(), adj[v].end(), i));
c[i] = v;
dfs(v);
size[u] += size[v];
if (size[v] > size[ce[adj[u][0]] ^ u]) {
swap(adj[u][0], i);
}
}
};
dfs(0);
int t = 0;
dfs = [&](int u) -> void {
dfn[u] = t++;
for (int i : adj[u]) {
int v = ce[i] ^ u;
top[v] = (i == adj[u][0] ? top[u] : v);
depth[v] = depth[u] + 1;
parent[v] = u;
dfs(v);
}
};
dfs(0);
parent[0] = -1;
}
int k = cv.size();
vector<vector<int>> ev(k);
for (auto [u, x] : cp) {
u = c[u];
x = lower_bound(cv.begin(), cv.end(), x) - cv.begin();
ev[x].emplace_back(u);
update(dfn[u], 1);
}
vector<int> s(q), t(q), x(q);
vector<int64_t> y(q);
for (int i = 0; i < q; i++) {
cin >> s[i] >> t[i] >> x[i] >> y[i];
s[i] -= 1;
t[i] -= 1;
}
vector<int> cnt(q);
for (int i = 0; i < q; i++) {
int u = s[i];
int v = t[i];
while (top[u] != top[v]) {
if (depth[top[u]] > depth[top[v]]) {
swap(u, v);
}
cnt[i] += query(dfn[v]) - query(dfn[top[v]] - 1);
v = parent[top[v]];
}
if (depth[u] > depth[v]) {
swap(u, v);
}
cnt[i] += query(dfn[v]) - query(dfn[u] - 1);
}
vector<int> mxa(q), last(q, -1);
vector<int64_t> rem = y;
vector<pair<int, int>> bs(q, make_pair(0, k));
while (true) {
bool fin = true;
vector<vector<int>> qr(k);
for (int i = 0; i < q; i++) {
if (bs[i].first < bs[i].second) {
int p = (bs[i].first + bs[i].second) / 2;
qr[p].emplace_back(i);
fin = false;
}
}
if (fin) {
break;
}
memset(f, 0, sizeof(f));
memset(af, 0, sizeof(af));
for (int i = 0; i < k; i++) {
for (int u : ev[i]) {
update(dfn[u], cv[i], 1);
}
for (int qi : qr[i]) {
int u = s[qi];
int v = t[qi];
int64_t sum = 0;
int num = 0;
while (top[u] != top[v]) {
if (depth[top[u]] > depth[top[v]]) {
swap(u, v);
}
auto [sum1, num1] = duo_query(dfn[v]);
auto [sum2, num2] = duo_query(dfn[top[v]] - 1);
sum += sum1 - sum2;
num += num1 - num2;
v = parent[top[v]];
}
if (depth[u] > depth[v]) {
swap(u, v);
}
auto [sum1, num1] = duo_query(dfn[v]);
auto [sum2, num2] = duo_query(dfn[top[v]] - 1);
sum += sum1 - sum2;
num += num1 - num2;
if (sum <= y[qi]) {
mxa[qi] = num;
last[qi] = i;
rem[qi] = y[qi] - sum;
bs[qi].first = i + 1;
}
else {
bs[qi].second = i;
}
}
}
}
for (int i = 0; i < q; i++) {
if (last[i] + 1 < k) {
x[i] -= (cnt[i] - mxa[i] - rem[i] / cv[last[i] + 1]);
}
x[i] = max(x[i], -1);
cout << x[i] << " \n"[i == n - 1];
}
return 0;
}
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:113:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
113 | for (auto [u, x] : cp) {
| ^
currencies.cpp:182:36: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
182 | auto [sum1, num1] = duo_query(dfn[v]);
| ^
currencies.cpp:183:36: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
183 | auto [sum2, num2] = duo_query(dfn[top[v]] - 1);
| ^
currencies.cpp:191:30: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
191 | auto [sum1, num1] = duo_query(dfn[v]);
| ^
currencies.cpp:192:30: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
192 | auto [sum2, num2] = duo_query(dfn[top[v]] - 1);
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
1884 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1884 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
1884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
1884 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
