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 ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 998244353;
const int N = 1e5;
int n, m, q;
vector<int > g[N+10];
vector< pair<int, int> > check, edge;
int depth[N+10], sub[N+10];
int up[N+10][18], sum[N+10][18];
int tin[N+10], tout[N+10];
vector<int> val[N+10];
int bigchild[N+10], pos[N+10], chain[N+10];
int timer = 1;
void dfs(int v, int par){
tin[v] = timer++;
up[v][0] = par;
for(int to : g[v]){
if(to == par) continue;
depth[to] = depth[v] + 1;
dfs(to, v);
sub[v]+= sub[to];
if(!bigchild[v] or sub[bigchild[v]] < sub[to]){
bigchild[v] = to;
}
}
sub[v] += 1, tout[v] = timer++;
}
int upper(int p, int a){
return (tin[p] <= tin[a] && tout[p] >= tout[a]);
}
int lca(int a, int b){
if(depth[b] < depth[a]) swap(a, b);
int k = depth[b] - depth[a];
for(int i = 0;i < 18; i++){
if(k & (1<<i)) b = up[b][i];
}
if(a == b) return a;
for(int i = 17; i >= 0; i--){
if(up[b][i] != up[a][i]){
a = up[a][i];
b = up[b][i];
}
}
if(a == b) return a;
return up[a][0];
}
void dfs2(int v, int par, int head){
pos[v] = timer++;
chain[v] = head;
if(bigchild[v]){
dfs2(bigchild[v], v, head);
}
for(int to : g[v]){
if(to == par || to == bigchild[v]) continue;
dfs2(to, v, to);
}
}
/*
int query(int a, int b){
if(chain[a] > chain[b]) swap(a, b);
int sum = 0;
while(chain[a] != chain[b]){
if(chain[a] > chain[b]) swap(a, b);
int l =pos[chain[b]], r = pos[b];
//sum+= get(l, r, 1, 1, n);
b = up[chain[b]][0];
}
if(chain[a] > chain[b]) swap(a, b);
int l = pos[a], r = pos[b];
//sum+= get(l, r, 1, 1, n);
return sum;
}
*/
/*
8 7 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 4
3 7
2 10
5 2
4 1
4 4
5 6
3 7 2 31
*/
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
for(int i = 1;i < n; i++){
int a, b; cin >> a >> b;
edge.push_back({a, b});
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1, 1);
timer = 1;
dfs2(1, 1, 1);
int coins = 0;
for(int i = 0;i < m; i++){
int p, c; cin >> p >> c;
check.push_back({p, c});
int a = edge[p-1].ff, b = edge[p-1].ss;
if(depth[a] < depth[b]) swap(a, b);
//cout << a << " , " << b << " = " << c << '\n';
sum[a][0] += 1;
val[a].push_back(c);
coins = c;
}
for(int j = 1;j < 18; j++){
for(int i = 1;i <= n; i++){
up[i][j] = up[up[i][j-1]][j-1];
sum[i][j] = sum[i][j-1] + sum[up[i][j-1]][j-1];
}
}
if(max({n, m, q}) <= 2000){
while(q--){
int s, t; cin >> s >> t;
int x, y; cin >> x >> y;
int lc = lca(s, t);
vector<pair<int, int> > vec;
while(s != lc){
for(int sa : val[s]) vec.push_back({sa, 1});
s = up[s][0];
}
while(t != lc){
for(int sa : val[t]) vec.push_back({sa, 1});
t = up[t][0];
}
//cout << "ancestor : ";
//cout << lc << "\n";
sort(all(vec), [&](auto A, auto B){
return A.ff < B.ff;
});
for(auto [silver, gold] : vec){
// cout << silver << ' ' << gold << ", ";
if(y >= silver){
y-= silver;
}else{
x-= gold;
}
}
//cout << '\n';
cout << max(-1LL, x) << '\n';
}
return 0;
}else{
}
return 0;
}
Compilation message (stderr)
currencies.cpp: In function 'int main()':
currencies.cpp:125:6: warning: variable 'coins' set but not used [-Wunused-but-set-variable]
125 | int coins = 0;
| ^~~~~
# | 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... |