Submission #1247302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247302		wcarrotw	Two Currencies (JOI23_currencies)	C++17	10 / 100	5094 ms	38916 KiB

currencies

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

const int MAXN = 100005;
const int LOG = 17;

struct Edge { int to, id; };

int N, M, Q;
vector<Edge> g[MAXN];
vector<vector<int>> edgeChk; // edgeChk[i] = checkpoint list of edge i

int depth[MAXN], parent[MAXN][LOG];
long long sumSilver[MAXN][LOG];
int edgeToParent[MAXN]; // edge id connecting v -> parent[v][0]

void dfs(int u, int p, int peid) {
    edgeToParent[u] = peid;
    for (auto &e : g[u]) {
        int v = e.to, eid = e.id;
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        parent[v][0] = u;
        sumSilver[v][0] = 0;
        for (int c : edgeChk[eid])
            sumSilver[v][0] += c;
        dfs(v, u, eid);
    }
}

void build() {
    depth[1] = 0;
    parent[1][0] = 1;
    sumSilver[1][0] = 0;
    edgeToParent[1] = -1; // root has no incoming edge
    dfs(1, 0, -1);
    for (int k = 1; k < LOG; ++k) {
        for (int v = 1; v <= N; ++v) {
            int mid = parent[v][k-1];
            parent[v][k] = parent[mid][k-1];
            sumSilver[v][k] = sumSilver[v][k-1] + sumSilver[mid][k-1];
        }
    }
}

pair<long long, vector<int>> climb(int u, int dist) {
    long long tot = 0;
    vector<int> collected;
    for (int k = LOG - 1; k >= 0; --k) {
        if ((1 << k) <= dist) {
            tot += sumSilver[u][k];
            // get checkpoints from u up to parent[u][k]
            int curr = u;
            for (int i = 0; i < (1 << k); ++i) {
                int eid = edgeToParent[curr];
                if (eid != -1) {
                    for (int c : edgeChk[eid]) collected.push_back(c);
                }
                curr = parent[curr][0];
            }
            u = curr;
            dist -= (1 << k);
        }
    }
    return {tot, collected};
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for (int k = 0; k < LOG; ++k)
        if (diff & (1 << k)) u = parent[u][k];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; --k) {
        if (parent[u][k] != parent[v][k]) {
            u = parent[u][k];
            v = parent[v][k];
        }
    }
    return parent[u][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M >> Q;
    vector<pair<int,int>> edges(N-1);
    for (int i = 0; i < N-1; ++i) {
        int a, b;
        cin >> a >> b;
        edges[i] = {a, b};
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }

    edgeChk.assign(N-1, {});
    for (int i = 0; i < M; ++i) {
        int p;
        long long c;
        cin >> p >> c;
        edgeChk[p-1].push_back((int)c);
    }

    build();

    while (Q--) {
        int s, t;
        long long X, Y;
        cin >> s >> t >> X >> Y;
        int anc = lca(s, t);

        auto [s1, c1] = climb(s, depth[s] - depth[anc]);
        auto [s2, c2] = climb(t, depth[t] - depth[anc]);

        long long totalSilver = s1 + s2;
        vector<int> all = c1;
        all.insert(all.end(), c2.begin(), c2.end());

        if (totalSilver <= Y) {
            cout << X << '\n';
            continue;
        }

        int need = totalSilver - Y;
        if ((int)all.size() > X) {
            nth_element(all.begin(), all.begin() + X, all.end(), greater<int>());
            all.resize(X);
        }
        sort(all.begin(), all.end(), greater<int>());

        int usedGold = 0;
        for (int c : all) {
            if (totalSilver <= Y) break;
            totalSilver -= c;
            usedGold++;
        }

        if (totalSilver <= Y && usedGold <= X)
            cout << (X - usedGold) << '\n';
        else
            cout << -1 << '\n';
    }

    return 0;
}

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