제출 #1345906

#제출 시각아이디문제언어결과실행 시간메모리
1345906phanvinhTwo Currencies (JOI23_currencies)C++20
100 / 100
1595 ms61980 KiB
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int oo = 1e18;
const int logg = 21;
int n, m, q;
vector<int> adj[maxn];
pair<int, int> E[maxn];
pair<int, int> Q[maxn];
// prepare PBS
int L[maxn], R[maxn], ans[maxn];
vector<int> bucket[maxn];
// Query
int S[maxn], T[maxn], X[maxn], Y[maxn];
// build tree BIT

struct Fenwick{
    int bit[maxn];
    void FILL(void){
        memset(bit, 0, sizeof bit);
    }
    void update(int pos, int val){
        for(; pos <= n; pos += pos & (-pos)) bit[pos] += val;
    }
    int get(int pos){
        int ans = 0;
        for(; pos > 0; pos -= pos & (-pos)) ans += bit[pos];
        return ans;
    }
} BIT1, BIT2;
// build LCA
int par[maxn][logg], depth[maxn], tin[maxn], tout[maxn];
void dfs(int u, int pa){
    tin[u] = ++tin[0];
    for(int v : adj[u]){
        if(v == pa) continue;
        depth[v] = depth[u] + 1;
        par[v][0] = u;
        dfs(v, u);
    }
    tout[u] = tin[0];
}

int LCA(int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    for(int j = logg - 1; j >= 0; j--){
        if(depth[par[u][j]] >= depth[v]) u = par[u][j];
    }
    if(u == v) return u;
    for(int j = logg - 1; j >= 0; j--){
        if(par[u][j] != par[v][j]){
            u = par[u][j];
            v = par[v][j];
        }
    }
    return par[u][0];
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    //freopen ("tree.inp" , "r" ,stdin);
    //freopen ("tree.out" , "w" ,stdout);
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        E[i] = {u, v};
    }

    par[1][0] = 1;
    dfs(1, 0);
    for(int j = 1; j < logg; j++){
        for(int i = 1; i <= n; i++){
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }

    for(int i = 1; i < n; i++){
        if(LCA(E[i].first, E[i].second) == E[i].second) swap(E[i].first, E[i].second);
    }

    for(int i = 1; i <= m; i++){
        cin >> Q[i].first >> Q[i].second;
        swap(Q[i].first, Q[i].second);
    }
    sort(Q + 1, Q + m + 1);

    for(int i = 1; i <= q; i++){
        cin >> S[i] >> T[i] >> X[i] >> Y[i];
        L[i] = 0;
        R[i] = m;
    }

    bool process = true;
    while(process){
        for(int i = 0; i <= m; i++) bucket[i].clear();
        BIT1.FILL();
        BIT2.FILL();
        process = false;
        for(int i = 1; i <= q; i++){
            if(L[i] <= R[i]){
                int mid = (L[i] + R[i]) / 2;
                bucket[mid].push_back(i);
                process = true;
            }
        }
        if(!process) break;
        for(int i = 1; i <= m; i++){
            int u = E[Q[i].second].second;
            BIT1.update(tin[u], 1);
            BIT1.update(tout[u] + 1, - 1);
        }
        for(int i = 0; i <= m; i++){
            if(i > 0){
                int u = E[Q[i].second].second;
                BIT1.update(tin[u], -1);
                BIT1.update(tout[u] + 1, 1);
                BIT2.update(tin[u], Q[i].first);
                BIT2.update(tout[u] + 1, -Q[i].first);
            }
            for(int id : bucket[i]){
                int total = BIT2.get(tin[S[id]]) + BIT2.get(tin[T[id]]) - 2 * BIT2.get(tin[LCA(S[id], T[id])]);
                if(total <= Y[id]){
                    ans[id] = BIT1.get(tin[S[id]]) + BIT1.get(tin[T[id]]) - 2 * BIT1.get(tin[LCA(S[id], T[id])]);
                    L[id] = i + 1;
                }
                else R[id] = i - 1;
            }
        }
    }
    for(int i = 1; i <= q; i++){
        cout << max(-1LL, X[i] - ans[i]) << '\n';
    }
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...