This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l + r) >> 1)
const int N = 100'005, inf = 1e18;
int anc[N][17], st[N], en[N], t;
ll h[N];
vector<array<int, 2>> adj[N];
array<ll, 2> a[N];
void dfs(int i, int par, ll d) {
h[i] = d;
anc[i][0] = par;
for (int j = 1; j < 17; j++) {
anc[i][j] = anc[anc[i][j - 1]][j - 1];
}
st[i] = t++;
for (auto [nxt, w] : adj[i]) {
if (nxt == par) continue;
dfs(nxt, i, d + w);
}
en[i] = t;
}
int getlca(int u, int v) {
if (st[u] > st[v]) swap(u, v);
if (st[u] <= st[v] && en[v] <= en[u]) {
return u;
}
for (int j = 16; j >= 0; j--) {
if (!(st[anc[u][j]] <= st[v] && en[v] <= en[anc[u][j]])) {
u = anc[u][j];
}
}
return anc[u][0];
}
struct node {
ll val = 0;
int cnt = 0;
node(int x) {
val = x, cnt = 1;
}
node() {}
node& operator+=(node y) {
val += y.val;
cnt += y.cnt;
return *this;
}
friend node operator+(node x, node y) {
return x += y;
}
node& operator-=(node y) {
val -= y.val;
cnt -= y.cnt;
return *this;
}
friend node operator-(node x, node y) {
return x -= y;
}
node& operator*=(int x) {
val *= x;
cnt *= x;
return *this;
}
friend node operator*(int x, node y) {
return y *= x;
}
};
node lazy[1 << 18];
void upd(int i, int l, int r, int s, int e, node v) {
if (s <= l && r <= e) {
lazy[i] += v;
return;
}
if (r < s || e < l) {
return;
}
upd(i << 1, l, mid, s, e, v);
upd(i << 1 | 1, mid + 1, r, s, e, v);
}
node get(int i, int l, int r, int x) {
if (l == r) {
return lazy[i];
}
if (x <= mid) {
return get(i << 1, l, mid, x) + lazy[i];
} else {
return get(i << 1 | 1, mid + 1, r, x) + lazy[i];
}
}
int n, m, q;
node height(int u) {
return get(1, 0, n - 1, st[u]);
}
vector<array<ll, 7>> ask[2][N];
vector<array<ll, 5>> ansask[N];
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> q;
array<int, 3> edges[n - 1];
for (int i = 0; i < n - 1; i++) {
auto &[u, v, cnt] = edges[i];
cin >> u >> v;
cnt = 0;
}
for (int i = 0; i < m; i++) {
cin >> a[i][1] >> a[i][0];
a[i][1]--;
edges[a[i][1]][2]++;
}
for (auto &[u, v, cnt] : edges) {
adj[u].push_back({v, cnt});
adj[v].push_back({u, cnt});
}
dfs(1, 1, 0);
for (auto &[u, v, cnt] : edges) {
if (st[u] > st[v]) {
swap(u, v);
}
}
sort(a, a + m);
array<ll, 4> query[q];
for (int i = 0; i < q; i++) {
auto &[u, v, x, y] = query[i];
cin >> u >> v >> y >> x;
ask[0][m >> 1].push_back({u, v, x, y, 0, m, i});
}
int cur = 0;
for (int _ = 0; _ < 17; _++) {
bool done = 0;
for (int i = 0; i < (1 << 18); i++) {
lazy[i] = node();
}
for (int md = 0; md <= m; md++) {
ask[cur ^ 1][md].clear();
}
int idx = -1;
for (int md = 0; md <= m; md++) {
if (md && idx + 1 < m) {
ll tar = a[idx + 1][0];
while (idx + 1 < m && a[idx + 1][0] == tar) {
idx++;
int e = a[idx][1];
int v = edges[e][1];
upd(1, 0, n - 1, st[v], en[v], a[idx][0]);
}
}
for (auto &[u, v, x, y, l, r, qidx] : ask[cur][md]) {
done = 1;
int lca = getlca(u, v);
node ttl = height(u) + height(v) - 2 * height(lca);
if (ttl.val <= x) {
l = md + 1;
} else {
r = md - 1;
}
if (l <= r) {
ask[cur ^ 1][(l + r) >> 1].push_back({u, v, x, y, l, r, qidx});
} else {
ansask[r].push_back({u, v, x, y, qidx});
}
}
}
if (!done) break;
cur ^= 1;
}
ll ans[q];
memset(ans, '?', sizeof ans);
int idx = -1;
for (int i = 0; i < (1 << 18); i++) {
lazy[i] = node();
}
for (int i = 0; i <= m; i++) {
if (i && idx + 1 < m) {
ll tar = a[idx + 1][0];
while (idx + 1 < m && a[idx + 1][0] == tar) {
idx++;
int e = a[idx][1];
int v = edges[e][1];
upd(1, 0, n - 1, st[v], en[v], a[idx][0]);
}
}
for (auto &[u, v, x, y, qidx] : ansask[i]) {
int lca = getlca(u, v);
node ttl = height(u) + height(v) - 2 * height(lca);
ll dist = h[u] + h[v] - 2 * h[lca];
x -= ttl.val;
dist -= ttl.cnt;
ll nxt = inf;
if (idx + 1 < m) {
nxt = a[idx + 1][0];
}
ll rem = min((ll)dist, x / nxt);
dist -= rem;
y -= dist;
ans[qidx] = y;
}
}
for (int i = 0; i < q; i++) {
if (ans[i] < 0) {
cout << "-1\n";
} else {
cout << ans[i] << '\n';
}
}
return 0;
}
Compilation message (stderr)
currencies.cpp:8:1: error: 'll' does not name a type
8 | ll h[N];
| ^~
currencies.cpp:10:7: error: 'll' was not declared in this scope
10 | array<ll, 2> a[N];
| ^~
currencies.cpp:10:12: error: template argument 1 is invalid
10 | array<ll, 2> a[N];
| ^
currencies.cpp:11:26: error: 'll' has not been declared
11 | void dfs(int i, int par, ll d) {
| ^~
currencies.cpp: In function 'void dfs(long long int, long long int, int)':
currencies.cpp:12:2: error: 'h' was not declared in this scope
12 | h[i] = d;
| ^
currencies.cpp: At global scope:
currencies.cpp:37:2: error: 'll' does not name a type
37 | ll val = 0;
| ^~
currencies.cpp: In constructor 'node::node(long long int)':
currencies.cpp:40:3: error: 'val' was not declared in this scope
40 | val = x, cnt = 1;
| ^~~
currencies.cpp: In member function 'node& node::operator+=(node)':
currencies.cpp:44:3: error: 'val' was not declared in this scope
44 | val += y.val;
| ^~~
currencies.cpp:44:12: error: 'struct node' has no member named 'val'
44 | val += y.val;
| ^~~
currencies.cpp: In member function 'node& node::operator-=(node)':
currencies.cpp:52:3: error: 'val' was not declared in this scope
52 | val -= y.val;
| ^~~
currencies.cpp:52:12: error: 'struct node' has no member named 'val'
52 | val -= y.val;
| ^~~
currencies.cpp: In member function 'node& node::operator*=(long long int)':
currencies.cpp:60:3: error: 'val' was not declared in this scope
60 | val *= x;
| ^~~
currencies.cpp: At global scope:
currencies.cpp:94:14: error: 'll' was not declared in this scope
94 | vector<array<ll, 7>> ask[2][N];
| ^~
currencies.cpp:94:18: error: template argument 1 is invalid
94 | vector<array<ll, 7>> ask[2][N];
| ^
currencies.cpp:94:19: error: template argument 1 is invalid
94 | vector<array<ll, 7>> ask[2][N];
| ^~
currencies.cpp:94:19: error: template argument 2 is invalid
currencies.cpp:95:14: error: 'll' was not declared in this scope
95 | vector<array<ll, 5>> ansask[N];
| ^~
currencies.cpp:95:18: error: template argument 1 is invalid
95 | vector<array<ll, 5>> ansask[N];
| ^
currencies.cpp:95:19: error: template argument 1 is invalid
95 | vector<array<ll, 5>> ansask[N];
| ^~
currencies.cpp:95:19: error: template argument 2 is invalid
currencies.cpp: In function 'int main()':
currencies.cpp:106:14: error: invalid types 'int[int]' for array subscript
106 | cin >> a[i][1] >> a[i][0];
| ^
currencies.cpp:106:25: error: invalid types 'int[int]' for array subscript
106 | cin >> a[i][1] >> a[i][0];
| ^
currencies.cpp:107:7: error: invalid types 'int[int]' for array subscript
107 | a[i][1]--;
| ^
currencies.cpp:108:13: error: invalid types 'int[int]' for array subscript
108 | edges[a[i][1]][2]++;
| ^
currencies.cpp:121:8: error: 'll' was not declared in this scope
121 | array<ll, 4> query[q];
| ^~
currencies.cpp:121:13: error: template argument 1 is invalid
121 | array<ll, 4> query[q];
| ^
currencies.cpp:123:9: error: cannot decompose non-array non-class type 'int'
123 | auto &[u, v, x, y] = query[i];
| ^~~~~~~~~~~~
currencies.cpp:125:18: error: request for member 'push_back' in 'ask[0][(m >> 1)]', which is of non-class type 'int'
125 | ask[0][m >> 1].push_back({u, v, x, y, 0, m, i});
| ^~~~~~~~~
currencies.cpp:134:21: error: request for member 'clear' in 'ask[(cur ^ 1)][md]', which is of non-class type 'int'
134 | ask[cur ^ 1][md].clear();
| ^~~~~
currencies.cpp:139:7: error: expected ';' before 'tar'
139 | ll tar = a[idx + 1][0];
| ^~~~
| ;
currencies.cpp:140:37: error: invalid types 'int[int]' for array subscript
140 | while (idx + 1 < m && a[idx + 1][0] == tar) {
| ^
currencies.cpp:140:44: error: 'tar' was not declared in this scope; did you mean 'tan'?
140 | while (idx + 1 < m && a[idx + 1][0] == tar) {
| ^~~
| tan
currencies.cpp:142:20: error: invalid types 'int[int]' for array subscript
142 | int e = a[idx][1];
| ^
currencies.cpp:144:43: error: invalid types 'int[int]' for array subscript
144 | upd(1, 0, n - 1, st[v], en[v], a[idx][0]);
| ^
currencies.cpp:147:53: error: 'begin' was not declared in this scope
147 | for (auto &[u, v, x, y, l, r, qidx] : ask[cur][md]) {
| ^
currencies.cpp:147:53: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from currencies.cpp:1:
/usr/include/c++/10/valarray:1224:5: note: 'std::begin'
1224 | begin(const valarray<_Tp>& __va)
| ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
from currencies.cpp:1:
/usr/include/c++/10/bits/fs_dir.h:549:3: note: 'std::filesystem::__cxx11::begin'
549 | begin(recursive_directory_iterator __iter) noexcept
| ^~~~~
currencies.cpp:147:53: error: 'end' was not declared in this scope
147 | for (auto &[u, v, x, y, l, r, qidx] : ask[cur][md]) {
| ^
currencies.cpp:147:53: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from currencies.cpp:1:
/usr/include/c++/10/valarray:1244:5: note: 'std::end'
1244 | end(const valarray<_Tp>& __va)
| ^~~
In file included from /usr/include/c++/10/filesystem:46,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
from currencies.cpp:1:
/usr/include/c++/10/bits/fs_dir.h:554:3: note: 'std::filesystem::__cxx11::end'
554 | end(recursive_directory_iterator) noexcept
| ^~~
currencies.cpp:151:13: error: 'struct node' has no member named 'val'
151 | if (ttl.val <= x) {
| ^~~
currencies.cpp:166:4: error: expected ';' before 'ans'
166 | ll ans[q];
| ^~~~
| ;
currencies.cpp:167:9: error: 'ans' was not declared in this scope; did you mean 'anc'?
167 | memset(ans, '?', sizeof ans);
| ^~~
| anc
currencies.cpp:174:6: error: expected ';' before 'tar'
174 | ll tar = a[idx + 1][0];
| ^~~~
| ;
currencies.cpp:175:36: error: invalid types 'int[int]' for array subscript
175 | while (idx + 1 < m && a[idx + 1][0] == tar) {
| ^
currencies.cpp:175:43: error: 'tar' was not declared in this scope; did you mean 'tan'?
175 | while (idx + 1 < m && a[idx + 1][0] == tar) {
| ^~~
| tan
currencies.cpp:177:19: error: invalid types 'int[int]' for array subscript
177 | int e = a[idx][1];
| ^
currencies.cpp:179:42: error: invalid types 'int[int]' for array subscript
179 | upd(1, 0, n - 1, st[v], en[v], a[idx][0]);
| ^
currencies.cpp:182:43: error: 'begin' was not declared in this scope
182 | for (auto &[u, v, x, y, qidx] : ansask[i]) {
| ^
currencies.cpp:182:43: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from currencies.cpp:1:
/usr/include/c++/10/valarray:1224:5: note: 'std::begin'
1224 | begin(const valarray<_Tp>& __va)
| ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
from currencies.cpp:1:
/usr/include/c++/10/bits/fs_dir.h:549:3: note: 'std::filesystem::__cxx11::begin'
549 | begin(recursive_directory_iterator __iter) noexcept
| ^~~~~
currencies.cpp:182:43: error: 'end' was not declared in this scope
182 | for (auto &[u, v, x, y, qidx] : ansask[i]) {
| ^
currencies.cpp:182:43: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from currencies.cpp:1:
/usr/include/c++/10/valarray:1244:5: note: 'std::end'
1244 | end(const valarray<_Tp>& __va)
| ^~~
In file included from /usr/include/c++/10/filesystem:46,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
from currencies.cpp:1:
/usr/include/c++/10/bits/fs_dir.h:554:3: note: 'std::filesystem::__cxx11::end'
554 | end(recursive_directory_iterator) noexcept
| ^~~
currencies.cpp:185:6: error: expected ';' before 'dist'
185 | ll dist = h[u] + h[v] - 2 * h[lca];
| ^~~~~
| ;
currencies.cpp:186:13: error: 'struct node' has no member named 'val'
186 | x -= ttl.val;
| ^~~
currencies.cpp:187:4: error: 'dist' was not declared in this scope
187 | dist -= ttl.cnt;
| ^~~~
currencies.cpp:188:6: error: expected ';' before 'nxt'
188 | ll nxt = inf;
| ^~~~
| ;
currencies.cpp:190:5: error: 'nxt' was not declared in this scope
190 | nxt = a[idx + 1][0];
| ^~~
currencies.cpp:190:21: error: invalid types 'int[int]' for array subscript
190 | nxt = a[idx + 1][0];
| ^
currencies.cpp:192:6: error: expected ';' before 'rem'
192 | ll rem = min((ll)dist, x / nxt);
| ^~~~
| ;
currencies.cpp:193:12: error: 'rem' was not declared in this scope; did you mean 'drem'?
193 | dist -= rem;
| ^~~
| drem