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;
struct Fenwick{
int n;
vector<int> fenw;
Fenwick(int sz){
n = sz;
fenw.resize(n+1, 0);
};
void add(int i, int x){
for(; i <= n; i+= i&-i){
fenw[i]+= x;
}
}
int pref(int i){
int s = 0;
for(; i > 0; i-= i & -i){
s+= fenw[i];
}
return s;
}
int sum(int l, int r){
return pref(r) - pref(l-1);
}
};
int n, m, q;
vector<int > g[N+10];
vector< pair<int, int> > edge;
int depth[N+10], up[N+10][20], sum[N+10][20];
int tin[N+10], tout[N+10], 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);
}
tout[v] = timer - 1;
}
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 < 20; i++){
if(k & (1<<i)) b = up[b][i];
}
if(a == b) return a;
for(int i = 19; i >= 0; i--){
if(up[b][i] != up[a][i]){
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
}
int ones(int a, int d){
int s = 0;
for(int i = 0;i < 20; i++){
if(d & (1<<i)){
s+= sum[a][i];
a = up[a][i];
}
}
return s;
}
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);
vector<array<int, 2> > adds;
for(int i = 0;i < m; i++){
int p, c; cin >> p >> c;
int a = edge[p-1].ff, b = edge[p-1].ss;
if(depth[a] < depth[b]) swap(a, b);
adds.push_back({a, c});
sum[a][0]+= 1;
}
sort(all(adds), [&](auto A, auto B){
return A[1] < B[1];
});
for(int j = 1;j < 20; j++){
for(int i = 1;i <= n; i++){
up[i][j] = up[up[i][j-1]][j-1];
sum[i][j] = sum[up[i][j-1]][j-1] + sum[i][j-1];
}
}
int s, t, x, y, lc;
/*vector<array<int, 4> > query;
vector<vector<int> > rn(n, vector<int>(2, {0, m+1}));
for(auto &A : query){
cin >> A[0] >> A[1] >> A[2] >> A[3];
}
* */
auto good=[&](int mid){
Fenwick f1(n + 1), f2(n + 1);
int idx = 0;
for(auto [a, c] : adds){
f1.add(tin[a], c);
f1.add(tout[a] + 1, -c);
f2.add(tin[a], 1);
f2.add(tout[a] + 1, -1);
if(idx == mid) break;
idx++;
}
int sum = f1.pref(tin[s]) + f1.pref(tin[t]) - 2 * f1.pref(tin[lc]);
int cnt = f2.pref(tin[s]) + f2.pref(tin[t]) - 2 * f2.pref(tin[lc]);
return make_pair(sum, cnt);
};
while(q--){
cin >> s >> t >> x >> y;
int l = 0, r = m + 1;
lc = lca(s, t);
int checkpoints = ones(s, depth[s] -depth[lc]) + ones(t, depth[t] - depth[lc]);
// cout << "overall there were : " << checkpoints << "\n";
while(l + 1 < r){
int mid = (l + r)>>1;
pair<int, int> ch = good(mid);
if(ch.ff <= y) l = mid;
else r = mid;
}
if(good(l).ff > y){
cout << max(-1LL, x - checkpoints) << '\n';
continue;
}
pair<int, int> ch = good(l);
// cout << ch.ss << " = ";
checkpoints-= ch.ss;
cout << max(-1LL, x - checkpoints) << '\n';
}
return 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... |