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>
#define MAX 100005
#define MOD 998244353
#define INF (ll)(1e18)
#define inf (1987654321)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef complex<long double> cpx;
constexpr long double PI = acos(-1);
int tt, n, m, k, q;
int in[MAX], out[MAX], dep[MAX];
int parent[MAX][20];
int lo[MAX], hi[MAX];
int ans[MAX];
vector<pii> edge;
vector<pii> chkpoint;
vector<pair<pii, pll> > inp;
vector<int> graph[MAX];
vector<int> event[MAX];
ll seg[MAX << 2];
void init(int str, int ed, int node) {
seg[node] = 0;
if(str == ed) return;
int mid = str + ed >> 1;
init(str, mid, node << 1);
init(mid + 1, ed, node << 1 | 1);
}
void update(int str, int ed, int left, int right, ll val, int node) {
if(str > right || ed < left) return;
if(left <= str && ed <= right) {
seg[node] += val;
return;
}
int mid = str + ed >> 1;
update(str, mid, left, right, val, node << 1);
update(mid + 1, ed, left, right, val, node << 1 | 1);
}
ll query(int str, int ed, int idx, int node) {
if(str == ed) return seg[node];
int mid = str + ed >> 1;
if(idx <= mid) return query(str, mid, idx, node << 1) + seg[node];
else return query(mid + 1, ed, idx, node << 1 | 1) + seg[node];
}
int pv = 0;
void dfs(int node, int par) {
parent[node][0] = par; in[node] = ++pv;
for(auto v : graph[node]) {
if(v == par) continue;
dep[v] = dep[node] + 1;
dfs(v, node);
}
out[node] = pv;
}
int lca(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
int diff = dep[a] - dep[b], j = 0;
while(diff) {
if(diff & 1) a = parent[a][j];
diff >>= 1; ++j;
}
if(a == b) return a;
for(int i = 19; i >= 0; --i) {
if(parent[a][i] == parent[b][i]) continue;
a = parent[a][i];
b = parent[b][i];
}
return parent[a][0];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> q;
edge.resize(n - 1);
for(int i = 0; i < n - 1; ++i) {
int a, b; cin >> a >> b;
edge[i] = {a, b};
graph[a].push_back(b);
graph[b].push_back(a);
}
chkpoint.resize(m);
for(int i = 0; i < m; ++i) cin >> chkpoint[i].second >> chkpoint[i].first;
for(int i = 0; i < m; ++i) chkpoint[i].second--;
sort(chkpoint.begin(), chkpoint.end());
inp.resize(q);
for(int i = 0; i < q; ++i) cin >> inp[i].first.first >> inp[i].first.second >> inp[i].second.first >> inp[i].second.second;
for(int i = 0; i < q; ++i) lo[i] = -1, hi[i] = m;
dfs(1, 0);
for(int i = 1; i <= n; ++i) for(int j = 1; j < 20; ++j) parent[i][j] = parent[parent[i][j - 1]][j - 1];
while(true) {
int flag = 1;
for(int i = 0; i < m; ++i) event[i].clear();
for(int i = 0; i < q; ++i) {
if(lo[i] + 1 == hi[i]) continue;
flag = 0;
int mid = lo[i] + hi[i] >> 1;
event[mid].push_back(i);
}
if(flag) break;
init(1, n, 1);
for(int i = 0; i < m; ++i) {
int j = chkpoint[i].second;
int u = edge[j].first, v = edge[j].second;
if(dep[u] < dep[v]) swap(u, v);
update(1, n, in[u], out[u], chkpoint[i].first, 1);
for(auto k : event[i]) {
int a = inp[k].first.first, b = inp[k].first.second;
int p = lca(a, b);
ll sum = query(1, n, in[a], 1);
sum += query(1, n, in[b], 1);
sum -= 2 * query(1, n, in[p], 1);
if(sum <= inp[k].second.second) lo[k] = i;
else hi[k] = i;
}
}
}
for(int i = 0; i < m; ++i) event[i].clear();
for(int i = 0; i < q; ++i) {
if(lo[i] == -1) continue;
event[lo[i]].push_back(i);
}
init(1, n, 1);
for(int i = m - 1; i >= 0; --i) {
for(auto k : event[i]) {
int a = inp[k].first.first, b = inp[k].first.second;
int p = lca(a, b);
ll sum = query(1, n, in[a], 1);
sum += query(1, n, in[b], 1);
sum -= 2 * query(1, n, in[p], 1);
if(sum <= inp[k].second.first) ans[k] = inp[k].second.first - sum;
else ans[k] = -1;
}
int j = chkpoint[i].second;
int u = edge[j].first, v = edge[j].second;
if(dep[u] < dep[v]) swap(u, v);
update(1, n, in[u], out[u], 1, 1);
}
for(int i = 0; i < q; ++i) {
if(lo[i] != -1) continue;
int a = inp[i].first.first, b = inp[i].first.second;
int p = lca(a, b);
ll sum = query(1, n, in[a], 1);
sum += query(1, n, in[b], 1);
sum -= 2 * query(1, n, in[p], 1);
if(sum <= inp[i].second.first) ans[i] = inp[i].second.first - sum;
else ans[i] = -1;
}
for(int i = 0; i < q; ++i) cout << ans[i] << '\n';
return 0;
}
Compilation message (stderr)
currencies.cpp: In function 'void init(int, int, int)':
currencies.cpp:32:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | int mid = str + ed >> 1;
| ~~~~^~~~
currencies.cpp: In function 'void update(int, int, int, int, ll, int)':
currencies.cpp:43:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid = str + ed >> 1;
| ~~~~^~~~
currencies.cpp: In function 'll query(int, int, int, int)':
currencies.cpp:50:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int mid = str + ed >> 1;
| ~~~~^~~~
currencies.cpp: In function 'int main()':
currencies.cpp:114:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
114 | int mid = lo[i] + hi[i] >> 1;
| ~~~~~~^~~~~~~
# | 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... |