Submission #1312326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312326		1ota	Two Currencies (JOI23_currencies)	C++20	100 / 100	2536 ms	215120 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
 
#define endl "\n"
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define entire(x) (x).begin(), (x).end()
 
const int inf = 9e18;
 
struct DDA {
    int n = 1;
    vector<int> Tree;
 
    DDA (int N) {
        ++N; while (n < N) n <<= 1;
        Tree.resize(2 * n, 0);
    }
 
    void update (int i, int delta){
        for (i += n; i > 0; i >>= 1) Tree[i] += delta;
    }
 
    int query (int l, int r){ // [l, r]
        int res = 0;
        for (l += n, r += n; l <= r; l >>= 1, r >>= 1){
            if (l & 1) res += Tree[l++];
            if (!(r & 1)) res += Tree[r--];
        } return res;
    }
};
 
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
 
    int n, m, q; cin >> n >> m >> q;
    vector<pii> edge(n-1);
    vector<vector<int>> adj(n), Adj(n);
    for (int i = 0; i < n-1; i++){
        int u, v; cin >> u >> v; u--, v--;
        Adj[u].push_back(v); Adj[v].push_back(u);
        edge[i] = pii{u, v};
    }
 
    vector<int> tin(n), tout(n);
    int timer = 0, logn = 2 + log2(n);
    vector<vector<int>> pi(n, vector<int>(logn, 0));
    auto reroot = [&](auto&& self, int s, int parent) -> void{
        tin[s] = timer++; pi[s][0] = parent;
        for (int i = 1; i < logn; i++) pi[s][i] = pi[pi[s][i-1]][i-1];
 
        for (auto u : Adj[s]) if (u != parent){
            adj[s].push_back(u); self(self, u, s); 
        } tout[s] = timer;
    }; reroot(reroot, 0, 0);
 
    while (true) { break; }
 
    auto isAnc = [&](int anc, int u){
        return (tin[anc] <= tin[u] and tout[u] <= tout[anc]);
    };
 
    auto lca = [&](int u, int v){
        if (isAnc(u, v) or isAnc(v, u)) return isAnc(u, v) ? u : v;
        for (int i = logn-1; i > -1; i--){
            if (!isAnc(pi[u][i], v)) u = pi[u][i];
        } return pi[u][0];
    };
 
    for (auto& [u, v] : edge) if (isAnc(v, u)) swap(u, v);
 
    vector<pii> t(m);
    for (int i = 0; i < m; i++){
        int p, c; cin >> p >> c; p--;
        int v = edge[p].ss;
        t[i] = pii{c, v};
    } sort(entire(t));
 
    vector<array<int, 4>> qn(q); // x gold, y silver
    for (auto& [u, v, x, y] : qn) cin >> u >> v >> x >> y, u--, v--;
 
    DDA cnt(n), et(n);
 
    auto psum = [&](int u, int v){
        int anc = lca(u, v), ea = et.query(0, tin[anc]);
        int pu = et.query(0, tin[u]), pv = et.query(0, tin[v]);
        return pu + pv - 2 * ea; 
    };
 
    auto pcnt = [&](int u, int v){
        int anc = lca(u, v), ca = cnt.query(0, tin[anc]);
        int cu = cnt.query(0, tin[u]), cv = cnt.query(0, tin[v]);
        return cu + cv - 2 * ca;
    };
 
    auto add = [&](int i){
        auto [w, v] = t[i];
        et.update(tin[v], +w); et.update(tout[v], -w);
        cnt.update(tin[v], +1); cnt.update(tout[v], -1);
    };
 
    vector<deque<int>> bs(m);
    vector<pii> bound(q, pii{0, m-1});
    vector<int> mcost(q, inf), cmin(q, 0);
 
    for (int i = 0; i < q; i++) bs[m/2].push_back(i);
 
    auto reduce = [&](int i, vector<deque<int>>& nbs){
        auto [u, v, x, y] = qn[i]; 
        auto& [l, r] = bound[i];
        int mid = (l + r + 1) / 2, path = psum(u, v);
        if (!(l < r)){ cmin[i] = pcnt(u, v); mcost[i] = path; return;}
        if (path <= y) l = mid, cmin[i] = pcnt(u, v), mcost[i] = path;
        else r = mid - 1;
        mid = (l + r + 1) / 2; nbs[mid].push_back(i);
    };
 
    int logm = 2 + log2(m);
    for (int depth = 0; depth <= logm; depth++){
        vector<deque<int>> nbs(m);
        fill(entire(cnt.Tree), 0ll); fill(entire(et.Tree), 0ll);
        for (int i = 0; i < m; i++){
            add(i); while (!bs[i].empty()) reduce(bs[i].back(), nbs), bs[i].pop_back();
        } bs = nbs;
    }
 
    fill(entire(cnt.Tree), 0ll); fill(entire(et.Tree), 0ll);
    for (int i = 0; i < m; i++) add(i);
 
    vector<int> ans(q);
    for (int i = 0; i < q; i++){
        auto [u, v, x, y] = qn[i];
        if (mcost[i] <= y) ans[i] = pcnt(u, v) - cmin[i];
        else ans[i] = pcnt(u, v);
        ans[i] = (ans[i] <= x) ? (x - ans[i]) : -1;
    }
 
    for (auto val : ans) cout << val << endl;
    return 0;
}

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