Submission #1242883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242883		Hamed_Ghaffari	Two Currencies (JOI23_currencies)	C++20	0 / 100	5 ms	6724 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define X first
#define Y second

const int MXN = 1e5+5, LOG = 17;

int n;

template<typename T> struct Fen {
    T fen[MXN];
    inline void upd(int s, int e, T x) {
        for(++s; s<=n; s+=s&-s) fen[s] += x;
        for(++e; e<=n; e+=e&-e) fen[e] -= x;
    }
    inline T get(int p) {
        T res=0;
        for(++p; p; p-=p&-p) res += fen[p];
        return res;
    }
};

Fen<ll> f0;
Fen<int> f1;

vector<int> g[MXN];
int A[MXN], B[MXN], par[MXN], jp[MXN], h[MXN], stt[MXN], fnt[MXN], timer;

void dfs(int v) {
    jp[v] = h[jp[jp[par[v]]]] - h[jp[par[v]]] == h[jp[par[v]]] - h[par[v]] ? jp[jp[par[v]]] : par[v];
    stt[v] = timer++;
    for(int u : g[v])
        if(u!=par[v])
            par[u] = v,
            h[u] = h[v]+1,
            dfs(u);
    fnt[v] = timer;
}
inline int jump(int v, int d) {
    if(d==h[v]) return v;
    while(h[par[v]]>d)
        v = h[jp[v]]>d ? jp[v] : par[v];
    return par[v];
}
inline int LCA(int u, int v) {
    if(h[u]<h[v]) swap(u, v);
    u = jump(u, h[v]);
    if(u==v) return u;
    while(par[u]!=par[v])
        if(jp[u]==jp[v]) u=par[u], v=par[v];
        else u=jp[u], v=jp[v];
    return par[u];
}

inline void upd(int v, ll x) {
    f0.upd(stt[v], fnt[v], x);
    f1.upd(stt[v], fnt[v], 1);
}
inline pair<ll, int> get(int u, int v) {
    int lca = LCA(u, v);
    return {
        f0.get(stt[u]) + f0.get(stt[v]) - 2*f0.get(stt[lca]),
        f1.get(stt[u]) + f1.get(stt[v]) - 2*f1.get(stt[lca])
    };
}
inline void clear() {
    memset(f0.fen, 0, sizeof(f0.fen));
    memset(f1.fen, 0, sizeof(f1.fen));
}

int m, q, P[MXN], C[MXN], sq[MXN], tq[MXN], xq[MXN], yq[MXN], L[MXN], R[MXN], ans[MXN], ord[MXN];
vector<int> vec[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m >> q;
    for(int i=1; i<=n-1; i++) {
        cin >> A[i] >> B[i];
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    par[0] = 0;
    dfs(1);
    clear();
    for(int i=1; i<=m; i++) {
        cin >> P[i] >> C[i];
        P[i] = A[P[i]]==par[B[P[i]]] ? B[P[i]] : A[P[i]];
        ord[i] = i;
        upd(P[i], 0);
    }
    sort(ord+1, ord+m+1, [&](int i, int j) {
        return C[i] < C[j];
    });
    for(int i=1; i<=q; i++) {
        cin >> sq[i] >> tq[i] >> xq[i] >> yq[i];
        L[i] = 0, R[i] = m+1;
        ans[i] = get(sq[i], tq[i]).Y;
    }
    while(1) {
        clear();
        for(int i=1; i<=m; i++) vec[i].clear();
        bool fnd = 0;
        for(int i=1; i<=q; i++)
            if(R[i]-L[i]>1) {
                fnd = 1;
                vec[(L[i]+R[i])>>1].push_back(i);
            }
        if(!fnd) break;
        for(int i=1; i<=m; i++) {
            upd(P[ord[i]], C[ord[i]]);
            for(int j : vec[i])
                (get(sq[j], tq[j]).X<=yq[j] ? L[j] : R[j]) = i;
        }
    }
    clear();
    for(int i=1; i<=m; i++) vec[i].clear();
    for(int i=1; i<=q; i++) vec[L[i]].push_back(i);
    for(int i=0; i<=m; i++) {
        if(i) upd(P[ord[i]], 0);
        for(int j : vec[i]) {
            int cnt = get(sq[j], tq[j]).Y;
            ans[j] = max(-1, xq[j] - (ans[j]-cnt));
        }
    }
    for(int i=1; i<=q; i++) cout << ans[i] << '\n';
    return 0;
}

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