Submission #947547

#	Time	Username	Problem	Language	Result	Execution time	Memory
947547		vladilius	Two Currencies (JOI23_currencies)	C++17	100 / 100	644 ms	58992 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
using pii = pair<int, int>;
 
struct FT{
    vector<ll> a;
    int n;
    FT(int ns){
        n = ns;
        a.resize(n + 1);
    }
    ll get(int v){
        ll out = 0;
        while (v > 0){
            out += a[v];
            v = (v & (v + 1)) - 1;
        }
        return out;
    }
    void upd(int p, int v){
        while (p <= n){
            a[p] += v;
            p |= (p + 1);
        }
    }
};
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, q; cin>>n>>m>>q;
    vector<pii> g[n + 1];
    vector<int> a(n), b(n);
    for (int i = 1; i < n; i++){
        cin>>a[i]>>b[i];
        g[a[i]].push_back({b[i], i});
        g[b[i]].push_back({a[i], i});
    }
    vector<int> p(m + 1), c(m + 1), C(n);
    vector<pii> f = {{0, 0}};
    for (int i = 1; i <= m; i++){
        cin>>p[i]>>c[i];
        C[p[i]]++;
        f.push_back({c[i], p[i]});
    }
    sort(f.begin(), f.end());
    vector<int> s(q + 1), t(q + 1), x(q + 1), y(q + 1), L(q + 1), R(q + 1);
    for (int i = 1; i <= q; i++){
        cin>>s[i]>>t[i]>>x[i]>>y[i];
        L[i] = 0;
        R[i] = m;
    }
    
    vector<int> pw[n + 1];
    int lg = ceil(log2(n));
    for (int i = 1; i <= n; i++){
        pw[i].resize(lg + 1);
    }
    vector<int> tin(n + 1), tout(n + 1), d(n + 1), dd(n + 1);
    int timer = 0;
    function<void(int, int)> dfs = [&](int v, int pr) -> void{
        tin[v] = ++timer;
        pw[v][0] = pr;
        for (int i = 1; i <= lg; i++){
            pw[v][i] = pw[pw[v][i - 1]][i - 1];
        }
        for (auto [i, j]: g[v]){
            if (i == pr) continue;
            dd[i] = dd[v] + C[j];
            d[i] = d[v] + 1;
            dfs(i, v);
        }
        tout[v] = timer;
    };
    dfs(1, 1);
    
    auto sub = [&](int x, int y) -> bool{
        return (tin[x] <= tin[y] && tout[x] >= tout[y]);
    };
    auto lca = [&](int x, int y) -> int{
        if (sub(x, y)) return x;
        if (sub(y, x)) return y;
        for (int i = lg; i >= 0; i--){
            if (!sub(pw[x][i], y)){
                x = pw[x][i];
            }
        }
        return pw[x][0];
    };
    
    vector<int> lc(q + 1);
    for (int i = 1; i <= q; i++){
        lc[i] = lca(s[i], t[i]);
    }
    
    auto ff = [&](int x, int y){
        if (d[x] > d[y]){
            return x;
        }
        return y;
    };
    
    while (true){
        bool ind = true;
        vector<int> check[m + 1];
        for (int i = 1; i <= q; i++){
            if (L[i] + 1 < R[i]){
                int m = (L[i] + R[i]) / 2;
                check[m].push_back(i);
                ind = false;
            }
        }
        if (ind) break;
        FT T(n);
        for (int i = 0; i <= m; i++){
            if (i > 0){
                auto [v, j] = f[i];
                j = ff(a[j], b[j]);
                T.upd(tin[j], v);
                T.upd(tout[j] + 1, -v);
            }
            for (int j: check[i]){
                ll sum = T.get(tin[s[j]]) + T.get(tin[t[j]]) - 2 * T.get(tin[lc[j]]);
                if (sum <= y[j]){
                    L[j] = i;
                }
                else {
                    R[j] = i - 1;
                }
            }
        }
    }
    vector<int> check[m + 1];
    for (int i = 1; i <= q; i++){
        check[R[i]].push_back(i);
    }
    FT T(n);
    for (int i = 0; i <= m; i++){
        if (i > 0){
            auto [v, j] = f[i];
            j = ff(a[j], b[j]);
            T.upd(tin[j], v);
            T.upd(tout[j] + 1, -v);
        }
        for (int j: check[i]){
            ll sum = T.get(tin[s[j]]) + T.get(tin[t[j]]) - 2 * T.get(tin[lc[j]]);
            if (sum <= y[j]){
                L[j] = R[j];
            }
        }
    }
    for (int i = 0; i <= m; i++) check[i].clear();
    for (int i = 1; i <= q; i++) check[L[i]].push_back(i);
    FT T1(n);
    vector<int> cnt(q + 1);
    for (int i = 0; i <= m; i++){
        if (i > 0){
            auto [v, j] = f[i];
            j = ff(a[j], b[j]);
            T1.upd(tin[j], 1);
            T1.upd(tout[j] + 1, -1);
        }
        for (int j: check[i]){
            cnt[j] = T1.get(tin[s[j]]) + T1.get(tin[t[j]]) - 2 * T1.get(tin[lc[j]]);
        }
    }
    
    for (int i = 1; i <= q; i++){
        int len = dd[s[i]] + dd[t[i]] - 2 * dd[lc[i]];
        len -= cnt[i];
        if (len > x[i]){
            cout<<-1<<"\n";
            continue;
        }
        cout<<x[i] - len<<"\n";
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32