Submission #1265619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265619		spetr	Two Currencies (JOI23_currencies)	C++20	10 / 100	5087 ms	14132 KiB

currencies

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

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

    ll n,m,q;
    if(!(cin >> n >> m >> q)) return 0;

    vector<pair<int,int>> edges; edges.reserve(max(0LL, n-1));
    vector<vector<pair<int,int>>> adj(n); // (neighbor, edge_index)

    for (int i = 0; i < n-1; ++i){
        int a,b; cin >> a >> b; --a; --b;
        edges.emplace_back(a,b);
        adj[a].push_back({b,i});
        adj[b].push_back({a,i});
    }

    vector<vector<ll>> price_per_edge(max(0ll, n-1));
    for (int i = 0; i < m; ++i){
        int eidx; ll val; cin >> eidx >> val; --eidx;
        if (eidx >= 0 && eidx < (int)price_per_edge.size()){
            price_per_edge[eidx].push_back(val);
        }
        // if invalid index in input, we ignore to avoid crash
    }

    // BFS from root 0 to compute parent (0-based), depth and parent_edge
    vector<int> parent(n, -1);
    vector<int> parent_edge(n, -1);
    vector<int> depth(n, 0);
    queue<int> qu;
    qu.push(0);
    parent[0] = -1;
    depth[0] = 0;
    while(!qu.empty()){
        int v = qu.front(); qu.pop();
        for (auto [to, eidx] : adj[v]){
            if (to == parent[v]) continue;
            parent[to] = v;
            parent_edge[to] = eidx;
            depth[to] = depth[v] + 1;
            qu.push(to);
        }
    }

    // Answer queries: gather all prices along path (using parent pointers), sort, greedy take by y
    while (q--){
        int a,b; ll x,y;
        cin >> a >> b >> x >> y; --a; --b;
        if (a < 0 || a >= n || b < 0 || b >= n){
            cout << "-1\n";
            continue;
        }

        vector<ll> collected;
        collected.clear();

        int u = a, v = b;
        // lift deeper one using parent pointers, collecting edge indices
        while (depth[u] > depth[v]){
            int e = parent_edge[u];
            if (e >= 0) {
                for (ll val : price_per_edge[e]) collected.push_back(val);
            }
            u = parent[u];
        }
        while (depth[v] > depth[u]){
            int e = parent_edge[v];
            if (e >= 0) {
                for (ll val : price_per_edge[e]) collected.push_back(val);
            }
            v = parent[v];
        }
        // now same depth, climb both until meet
        while (u != v){
            int eu = parent_edge[u];
            int ev = parent_edge[v];
            if (eu >= 0){
                for (ll val : price_per_edge[eu]) collected.push_back(val);
            }
            if (ev >= 0){
                for (ll val : price_per_edge[ev]) collected.push_back(val);
            }
            u = parent[u];
            v = parent[v];
        }

        // sort collected prices ascending and greedily spend y
        sort(collected.begin(), collected.end());
        ll i = 0;
        while (i < (ll)collected.size() && y >= collected[i]){
            y -= collected[i];
            ++i;
        }
        ll remaining = (ll)collected.size() - i;
        if (remaining > x){
            cout << "-1\n";
        } else {
            cout << (x - remaining) << "\n";
        }
    }

    return 0;
}

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