Submission #1247322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247322		azaylibelz	Two Currencies (JOI23_currencies)	C++20	0 / 100	5007 ms	33876 KiB

currencies

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9 + 7;
const ll infmax = ~(1LL << 64 - 1) / 10;
const ll infmin = (1LL << 64 - 1) / 10;
const ll maxq = 1e5 + 5, maxn = 1e5 + 5;

struct Query {
    ll id, s, t, x, y;
};
vector<pair<ll, ll>> adj[maxn];
vector<ll> checkpolls[maxn];
vector<Query> queries;

ll n, m, q;
ll res[maxq];
ll childSz[maxn];
bool removed[maxn];
vector<ll> compNode;

vector<ll> pathCost[maxn], pathpSum[maxn]; 
ll subPar[maxn];

void getCompNode(ll u, ll p) {
    compNode.push_back(u);
    for(auto &[v, w]: adj[u]) {
        if(v != p && !removed[v]) {
            getCompNode(v, u);
        }
    }
}

void dfsSz(ll u, ll p) {
    childSz[u] = 1;
    for(auto &[v, w]: adj[u]) {
        if(v != p && !removed[v]) {
            dfsSz(v, u);
            childSz[u] += childSz[v];
        }
    }
}

ll findCentroid(ll u, ll p, ll totalSz) {
    for(auto &[v, w]: adj[u]) {
        if(v != p && !removed[v] && childSz[v] * 2 > totalSz) {
            return findCentroid(v, u, totalSz);
        }
    }
    return u;
}

void getPathInfo(ll u, ll p, ll c, ll rt) {
    subPar[u] = rt;
    for(auto &[v, idx]: adj[u]) {
        if(v != p && !removed[v]) {
            pathCost[v] = pathCost[u];
            vector<ll> merged(pathCost[v].size() + checkpolls[idx].size());
            merge(pathCost[v].begin(), pathCost[v].end(), checkpolls[idx].begin(), checkpolls[idx].end(), merged.begin());
            pathCost[v] = merged;
            pathpSum[v].assign(pathCost[v].size() + 1, 0);
            for(ll i = 0; i < pathCost[v].size(); i++) {
                pathpSum[v][i + 1] = pathpSum[v][i] + pathCost[v][i];
            }
            getPathInfo(v, u, c, rt);
        }
    }
}

ll calc(ll s, ll t, ll kSliver) {
    auto& costS = pathCost[s];
    auto& costT = pathCost[t];
    auto& pss = pathpSum[s];
    auto& pst = pathpSum[t];
    if(kSliver > costS.size() + costT.size()) return infmax;
    ll res = infmax;
    for(ll i = 0; i <= costS.size(); i++) {
        ll j = kSliver - i;
        if(j >= 0 && j <= costT.size()) {
            res = min(res, pss[i] + pst[j]);
        }
    }
    return res;
}

void solve(ll entry, vector<Query>& queries, ll midGold, vector<bool>& ress) {
    if(queries.empty()) return;
    compNode.clear();
    getCompNode(entry, 0);
    ll totalSz = compNode.size();
    dfsSz(entry, 0);
    ll centroid = findCentroid(entry, 0, totalSz);
    pathCost[centroid].clear();
    pathpSum[centroid].assign(1, 0);
    subPar[centroid] = centroid;
    for(auto &[v, idx]: adj[centroid]) {
        if(!removed[v]) {
            pathCost[v] = checkpolls[idx];
            pathpSum[v].assign(pathCost[v].size() + 1, 0);
            for(ll i = 0; i < pathCost[v].size(); i++) {
                pathpSum[v][i + 1] = pathpSum[v][i] + pathCost[v][i];
            }
            getPathInfo(v, centroid, centroid, v);
        }
    }

    map<ll, vector<Query>> subQueries;
    vector<Query> crossQ;
    for(auto &q: queries) {
        if(subPar[q.s] == subPar[q.t]) {
            if(subPar[q.s] != centroid) {
                subQueries[subPar[q.s]].push_back(q);
            } else crossQ.push_back(q);
        } else crossQ.push_back(q);
    }

    for(auto &q: crossQ) {
        ll s = q.s, t = q.t;
        ll pcheckpolls = pathCost[s].size() + pathCost[t].size();
        ll kSliver = pcheckpolls - midGold;

        bool flag = false;
        if(kSliver < 0) flag = true;
        else {
            ll sliver = calc(s, t, kSliver);
            if(sliver < q.y) {
                flag = true;
            }
        }
        ress[q.id] = flag;
    }
    removed[centroid] = true;
    for(auto &[rt, qs]: subQueries) {
        solve(rt, qs, midGold, ress);
    }
}

void pbs(vector<Query> queries, ll mingold, ll maxgold) {
    if (queries.empty() || mingold > maxgold) {
        return;
    }
    ll midgold = mingold + (maxgold - mingold) / 2;
    vector<Query> possibleqs, impossibleqs;
    fill(removed + 1, removed + n + 1, false);
    vector<bool> results(q);
    solve(1, queries, midgold, results);

    for (const auto& q : queries) {
        if (results[q.id]) {
            res[q.id] = midgold;
            possibleqs.push_back(q);
        } else {
            impossibleqs.push_back(q);
        }
    }

    pbs(possibleqs, mingold, midgold - 1);
    pbs(impossibleqs, midgold + 1, maxgold);
}


signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m >> q;
    for (ll i = 1; i < n; ++i) {
        ll u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    for (ll i = 0; i < m; ++i) {
        ll p, c; cin >> p >> c;
        checkpolls[p].push_back(c);
    }
    for (ll i = 1; i < n; ++i) sort(checkpolls[i].begin(), checkpolls[i].end());
    for (ll i = 0; i < q; ++i) {
        ll s, t, x, y; cin >> s >> t >> x >> y;
        queries.push_back({i, s, t, x, y});
    }

    fill(res, res + q, -1);
    pbs(queries, 0, n);
    for (ll i = 0; i < q; ++i) {
        ll gold = res[i];
        if (gold != -1 && queries[i].x >= gold) {
            cout << queries[i].x - gold << "\n";
        } else {
            cout << -1 << "\n";
        }
    }

    return 0;
}

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