제출 #1247300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247300		wcarrotw	Two Currencies (JOI23_currencies)	C++17	10 / 100	787 ms	1114112 KiB

currencies

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

const int MAXN = 100000 + 5;
const int LOG = 17;

struct Edge { int to, id; };

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

int depth[MAXN], parent[MAXN][LOG];
long long sumSilver[MAXN][LOG];
vector<int> chkList[MAXN][LOG];

// Preprocess: build depth, parent[v][0], sumSilver[v][0], chkList[v][0]
void dfs(int u, int p) {
    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;
        // accumulate all checkpoints on this edge
        sumSilver[v][0] = 0;
        chkList[v][0].clear();
        for (int c : edgeChk[eid]) {
            sumSilver[v][0] += c;
            chkList[v][0].push_back(c);
        }
        dfs(v, u);
    }
}

void build() {
    // initialize root = 1
    depth[1] = 0;
    parent[1][0] = 1;
    sumSilver[1][0] = 0;
    chkList[1][0].clear();
    dfs(1, 0);
    // binary lifting
    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];
            chkList[v][k] = chkList[v][k-1];
            chkList[v][k].insert(
                chkList[v][k].end(),
                chkList[mid][k-1].begin(), chkList[mid][k-1].end()
            );
        }
    }
}

// climb u up by dist, return <total silver, list of checkpoint costs>
pair<long long, vector<int>> climb(int u, int dist) {
    long long tot = 0;
    vector<int> out;
    for (int k = LOG-1; k >= 0; --k) {
        if ((1 << k) <= dist) {
            tot += sumSilver[u][k];
            out.insert(out.end(), chkList[u][k].begin(), chkList[u][k].end());
            u = parent[u][k];
            dist -= (1 << k);
        }
    }
    return {tot, out};
}

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;
        }
        sort(all.rbegin(), all.rend());
        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