Submission #1247292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247292		quannnguyen2009	Two Currencies (JOI23_currencies)	C++20	100 / 100	1026 ms	58056 KiB

currencies

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 1e5+5, mod = 1e9+7, inf = 1e18, L = 17;

int n, m, q, timer;
vector<int> adj[N];
int in[N], out[N], d[N];
int up[N][L];
ii ed[N];
ii cp[N];
int s[N], t[N], x[N], y[N], lo[N], hi[N], ans[N], tot[N];
vector<int> lst[N];


struct FenwickTree {
    int n;
    vector<int> bit;

    void resz(int n_) {
        n = n_;
        bit.assign(n+1, 0);
    }

    int get(int p) {
        int idx = p, ans = 0;
        while (idx>0) {
            ans += bit[idx];
            idx -= (idx&(-idx));
        }
        return ans;
    }

    void upd(int u, int v) {
        int idx = u;
        while (idx<=n) {
            bit[idx]+=v;
            idx+=(idx&(-idx));
        }
    }
};

void dfs(int u, int p) {
    in[u] = ++timer;
    d[u] = d[p]+1;
    up[u][0] = p;
    for (int i=1; i<L; i++) up[u][i] = up[up[u][i-1]][i-1];
    for (int v: adj[u]) {
        if (v!=p) {
            dfs(v, u);
        }
    }
    out[u] = timer;
}

int kth_ancestor(int u, int k) {
    for (int i=0; i<L; i++) {
        if (k>>i&1) u = up[u][i];
    }
    return u;
}

int lca(int u, int v) {
    if (d[u]!=d[v]) {
        if (d[u]>d[v]) swap(u, v);
        v = kth_ancestor(v, d[v]-d[u]);
    }
    if (u==v) return u;
    for (int i=L-1; i>=0; i--) {
        if (up[u][i]!=up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    for (int i=1; i<n; i++) {
        int u, v; cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        ed[i] = {u, v};
    }
    dfs(1, 0);
    for (int i=1; i<n; i++) {
        if (in[ed[i].se]<=in[ed[i].fi] && out[ed[i].fi]<=out[ed[i].se]) swap(ed[i].fi, ed[i].se);
    }
    for (int i=1; i<=m; i++) {
        int p, c; cin >> p >> c;
        cp[i] = {c, ed[p].se};
    }
    sort(cp+1, cp+m+1);
    FenwickTree silver; silver.resz(n);
    for (int i=1; i<=q; i++) {
        cin >> s[i] >> t[i] >> x[i] >> y[i];
    }
    for (int i=1; i<=m; i++) {
        int node = cp[i].se;
        silver.upd(in[node], 1);
        silver.upd(out[node]+1, -1);
    }
    for (int i=1; i<=q; i++) {
        tot[i] = silver.get(in[s[i]])+silver.get(in[t[i]])-2*silver.get(in[lca(s[i], t[i])]);
    }
    FenwickTree gold;
    for (int i=1; i<=q; i++) lo[i] = 1, hi[i] = m;
    bool stop = 0;
    while (!stop) {
        stop = 1;
        for (int i=1; i<=m; i++) lst[i].clear();
        for (int i=1; i<=q; i++) {
            if (lo[i]<=hi[i]) {
                stop = 0;
                lst[(lo[i]+hi[i])>>1].pb(i);
            }
        }
        silver.resz(n);
        gold.resz(n);
        for (int i=1; i<=m; i++) {
            int node = cp[i].se, cost = cp[i].fi;
            silver.upd(in[node], cost);
            silver.upd(out[node]+1, -cost);
            gold.upd(in[node], 1);
            gold.upd(out[node]+1, -1);
            if (!sz(lst[i])) continue;
            for (int id: lst[i]) {
                int tmp = silver.get(in[s[id]])+silver.get(in[t[id]])-2*silver.get(in[lca(s[id], t[id])]);
                if (tmp<=y[id]) {
                    ans[id] = gold.get(in[s[id]])+gold.get(in[t[id]])-2*gold.get(in[lca(s[id], t[id])]);
                    lo[id] = i+1;
                } else {
                    hi[id] = i-1;
                }
            }
        }
    }
    for (int i=1; i<=q; i++) {
        int rem = tot[i]-ans[i];
        if (rem>x[i]) cout << -1 << '\n';
        else cout << x[i]-rem << '\n';
    }
}

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