제출 #1308081

#제출 시각아이디문제언어결과실행 시간메모리
1308081habelleTwo Currencies (JOI23_currencies)C++20
100 / 100
579 ms35992 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++)
#define FORNG(i,r,l) for(int i = (r), _l = (l); i >= _l; i--)
#define REP(i,r) for(int i = 0, _r = (r); i < _r; i++)
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define size(v) ((ll)(v).size())
#define all(v) (v).begin(),(v).end()
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
const ll MOD = 1e9 + 7, N = 2e5 + 36, LOG = 19;
const int INF = 1e9 + 36;
struct Fenwick{
    int n;
    vector<ll> fen;
    Fenwick(int n = 0):n(n){
        fen.assign(n + 1, 0);
    }
    void update(int p,ll v){
        for(;p <= n;p += p & -p)fen[p] += v;
    }
    ll get(int p){
        ll res = 0;
        for(;p;p-=p&-p)res += fen[p];
        return res;
    }
};
int n,m,q,S[N],T[N],L[N],R[N],G[N],ans[N];
int SS[N], finS[N];
ll X[N],Y[N];
pair<int,int> d[N], edge[N];
vector<int> adj[N];
int t,tin[N],tout[N],high[N];
int tpos,pos[N],MIHIGH[LOG + 1][N];
void predfs(int u,int par = -1){
    for(int v : adj[u])if(v != par){
        high[v] = high[u] + 1;
        predfs(v, u);
    }
}
void dfs(int u,int par = -1){
    tin[u] = ++t;
    pos[u] = ++tpos;
    MIHIGH[0][tpos] = u;
    for(int v : adj[u])if(v != par){
        SS[v] += SS[u];
        dfs(v, u);
        MIHIGH[0][++tpos] = u;
    }
    tout[u] = t;
}
#define MIN(u, v) (high[u] < high[v] ? u : v)
int LCA(int u,int v){
    if(pos[u] > pos[v])swap(u, v);
    int tmp = __lg(pos[v] - pos[u] + 1);
    return MIN(MIHIGH[tmp][pos[u]], MIHIGH[tmp][pos[v] - MASK(tmp) + 1]);
}
int main(){
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>q;
    FOR(i,1,n-1){
        int u,v;cin>>u>>v;
        edge[i] = {u, v};
        adj[u].pb(v);
        adj[v].pb(u);
    }

    predfs(1);

    FOR(i,1,m){
        cin>>d[i].se>>d[i].fi;
        int u = edge[d[i].se].fi, v = edge[d[i].se].se;
        if(high[u] > high[v])d[i].se = u;
        else d[i].se = v;
        SS[d[i].se]++;
    }

    dfs(1);

    FOR(j,1,LOG)FOR(i,1,tpos - MASK(j) + 1){
        MIHIGH[j][i] = MIN(MIHIGH[j - 1][i], MIHIGH[j - 1][i + MASK(j - 1)]);
    }

    sort(d + 1, d + 1 + m);

    FOR(i,1,q){
        cin>>S[i]>>T[i]>>X[i]>>Y[i];
        L[i] = 0;
        R[i] = m;
        G[i] = LCA(S[i], T[i]);
        finS[i] = SS[S[i]] + SS[T[i]] - SS[G[i]] * 2;
        ans[i] = INF;
    }

    vector<pair<int,int>> vec;

    while(1){
        Fenwick sum(n),cnt(n);
        vec.clear();
        FOR(i,1,q)if(L[i] <= R[i]){
            vec.pb({(L[i] + R[i]) >> 1, i});
        }
        if(vec.empty())break;
        sort(all(vec));
        int j = 1;
        REP(i,size(vec)){
            int mid = vec[i].fi, p = vec[i].se;
            while(j <= mid){
                int u = d[j].se, c = d[j].fi;
                sum.update(tin[u], c);
                sum.update(tout[u] + 1, -c);
                cnt.update(tin[u], 1);
                cnt.update(tout[u] + 1, -1);
                j++;
            }
            ll tot = sum.get(tin[S[p]]) + sum.get(tin[T[p]])
            - sum.get(tin[G[p]]) * 2;
            ll totcnt = cnt.get(tin[S[p]]) + cnt.get(tin[T[p]])
            - cnt.get(tin[G[p]]) * 2;
            if(tot <= Y[p]){
                ans[p] = finS[p] - totcnt;
                L[p] = mid + 1;
            }else{
                R[p] = mid - 1;
            }
        }
    }
    FOR(i,1,q)cout<<(X[i] - ans[i] < 0 ? -1 : X[i] - ans[i])<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...