Submission #1262021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262021		patgra	Two Currencies (JOI23_currencies)	C++20	38 / 100	5096 ms	55696 KiB

currencies

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int n, m, q;
vector<vector<pair<int, int>>> g;
vector<pair<int, int>> ogE;
vector<int> subS, inEu, eu, over;
vector<ll> qAvail, qAvail2, dep, answers;
vector<vector<int>> costs;
map<ll, int> edges;
int pret;
vector<bool> off;
int tB;
vector<ll> ts, t1;
int squirt;

void tAdd(int i, ll x, ll times) {
    i += tB;
    if(x < 0) x *= -1, times *= -1;
    DC << "  tAdd(" << i - tB << ' ' << x << ' ' << times << ")" << eol;
    ts[i] += x * times;
    t1[i] += times;
    while(i) i /= 2, ts[i] = ts[2 * i] + ts[2 * i + 1], t1[i] = t1[2 * i] + t1[2 * i + 1];
}

ll tQ(ll x) {
    int v = 1;
    ll ans = 0;
    while(v < tB) {
        v *= 2;
        if(ts[v] <= x) ans += t1[v], x -= ts[v], v++;
    }
    if(t1[v] && ts[v]) {
        ll base = ts[v] / t1[v];
        ans += min(x / base, t1[v]);
    }
    if(!ts[v]) ans += t1[v];
    return ans;
}

void dfs1(int v, int p) {
    subS[v] = 1;
    repIn2(u, c, g[v]) if(u != p && !off[u]) dfs1(u, v), subS[v] += subS[u], edges[c] = 1;
}

void dfs2(int v, int p, int cen, int ove) {
    subS[v] = 1;
    inEu[v] = pret;
    eu[pret++] = v;
    over[v] = ove;
    repIn2(u, c, g[v]) if(u != p && !off[u]) dep[u] = dep[v] + c, dfs2(u, v, cen, (v == cen ? u : ove)), subS[v] += subS[u], eu[pret++] = v;
}

bool mosCmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
    auto [al, ar] = a.first;
    auto [bl, br] = b.first;
    if(al / squirt == bl / squirt) return ((al / squirt) % 2) ? ar < br : ar > br;
    return al < bl;
}

void decompose(int v, vector<pair<pair<int, int>, int>>& queries) {
    edges.clear();
    dfs1(v, 0);
    edges.erase(0);
    int cen = v;
    bool found = false;
    while(!found) {
        found = true;
        repIn2(u, c, g[cen]) if(!off[u] && subS[u] * 2 > subS[v] && subS[u] < subS[cen]) { cen = u, found = false; break; }
    }

    v = cen;
    off[cen] = true;
    pret=0;
    dep[v] = 0;
    dfs2(v, 0, v, 0);
    vector<pair<pair<int, int>, int>> mq;
    vector<vector<pair<pair<int, int>, int>>> oq(pret);
    repIn2(ab, qi, queries) {
        auto [a, b] = ab;
        if(over[a] != over[b]) mq.pb({{min(inEu[a], inEu[b]), max(inEu[a], inEu[b])}, qi});
        else oq[inEu[over[a]]].pb({ab, qi});
    }
    queries.clear();

    int lt = 0;
    repIn2(k, vl, edges) vl = lt++;
    tB = 1 << (32 - __builtin_clz(max(2, lt) - 1));

    squirt = (int)sqrt(pret);
    ranges::sort(mq, mosCmp);
    int l = 0, r = 0;
    rep(i, 1, 2 * tB) ts[i] = t1[i] = 0;
    repIn2(ab, qi, mq) {
        auto [a, b] = ab;
        while(l > a) {
            int cv = eu[l];
            int u = eu[--l];
            if(dep[u] == dep[cv]) continue;
            tAdd(edges[abs(dep[u] - dep[cv])], dep[u] - dep[cv], 1);
        }
        while(r < b) {
            int cv = eu[r];
            int u = eu[++r];
            if(dep[u] == dep[cv]) continue;
            tAdd(edges[abs(dep[u] - dep[cv])], dep[u] - dep[cv], 1);
        }
        while(l < a) {
            int cv = eu[l];
            int u = eu[++l];
            if(dep[u] == dep[cv]) continue;
            tAdd(edges[abs(dep[u] - dep[cv])], dep[u] - dep[cv], 1);
        }
        while(r > b) {
            int cv = eu[r];
            int u = eu[--r];
            if(dep[u] == dep[cv]) continue;
            tAdd(edges[abs(dep[u] - dep[cv])], dep[u] - dep[cv], 1);
        }
        auto usable = tQ(qAvail[qi]);
        auto all = t1[1];
        DEBUG {
            DC << "For query " << qi << "\n interval eu (" << l << ' ' << r << "): ";
            rep(i, l, r + 1) DC << eu[i] << ' ';
            DC << "\n usable " << usable << "\n all " << all << eol;
        }
        if(usable + qAvail2[qi] < all) answers[qi] = -1;
        else answers[qi] = qAvail2[qi] - (all - usable);
    }

    mq.clear();
    off[v] = true;
    repIn2(u, c, g[v]) if(!off[u]) decompose(u, oq[inEu[u]]);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> m >> q;
    ll a, b, c, d;
    ogE.resize(n - 1);
    rep(i, 0, n - 1) cin >> ogE[i].first >> ogE[i].second;
    costs.resize(n - 1);
    rep(i, 0, m) {
        cin >> a >> b;
        costs[--a].pb(b);
    }

    int newNodes = 0;
    rep(i, 0, n - 1) newNodes += max(0, (int)costs[i].size() - 1);
    g.resize(n + 1 + newNodes);
    newNodes = 0;
    rep(i, 0, n - 1) {
        auto [x, y] = ogE[i];
        if(costs[i].empty()) {g[x].pb({y, 0}), g[y].pb({x, 0}); continue;}
        int last = x;
        rep(j, 0, (int)costs[i].size() - 1) g[last].pb({n + 1 + newNodes, costs[i][j]}), g[n + 1 + newNodes].pb({last, costs[i][j]}), last = n + 1 + newNodes++;
        g[last].pb({y, costs[i].back()}), g[y].pb({last, costs[i].back()});
    }
    DEBUG {
        DC << "Graph :\n";
        rep(i, 1, (int)g.size()) repIn2(j, cc, g[i]) DC << i << ' ' << j << ' ' << cc << eol;
        DC << eol;
    }

    n = (int)g.size();
    subS.resize(n);
    inEu.resize(n);
    eu.resize(2 * n + 5);
    over.resize(n);
    answers.resize(q);
    dep.resize(n);
    qAvail.resize(q);
    qAvail2.resize(q);
    off.resize(n);
    int maxTB = 1 << (32 - __builtin_clz(n + 1));
    ts.resize(2 * maxTB);
    t1.resize(2 * maxTB);

    vector<pair<pair<int, int>, int>> queries(q);
    rep(i, 0, q) {
        cin >> a >> b >> c >> d;
        queries[i] = {{a, b}, i};
        qAvail[i] = d;
        qAvail2[i] = c;
    }

    decompose(1, queries);
    rep(i, 0, q) cout << answers[i] << '\n';
}

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