Submission #805185

#	Time	Username	Problem	Language	Result	Execution time	Memory
805185		Sharky	Two Currencies (JOI23_currencies)	C++17	10 / 100	5074 ms	37780 KiB

currencies

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

#define int long long
#define sz(x) (int)x.size()
const int maxn = 1E5+8;

vector<pair<int, vector<int>>> adj[maxn];

struct edge {
    int u, v;
    vector<int> c;
};

vector<edge> edges;
map<pair<int, int>, int> mp;
int n, m, q, ls[maxn];

void dfs(int u, int pr = -1) {
    for (auto& [v, c] : adj[u]) {
        if (v == pr) continue;
        dfs(v, u);
        ls[v] = u;
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        edges.push_back((edge) {u, v, {}});
        mp[{u, v}] = mp[{v, u}] = i;
    }
    for (int i = 1; i <= m; i++) {
        int p, c;
        cin >> p >> c;
        edges[p-1].c.push_back(c);
    }
    for (auto& [u, v, c] : edges) {
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
    while (q--) {
        int s, t, x, y;
        cin >> s >> t >> x >> y;
        for (int i = 1; i <= n; i++) ls[i] = -1;
        vector<int> path, c;
        dfs(s);
        int bk = t;
        while (bk != -1) {
            path.push_back(bk);
            bk = ls[bk];
        }
        reverse(path.begin(), path.end());
        // for (int& e : path) cout << e << " ";
        // cout << "\n";
        for (int i = 0; i < sz(path) - 1; i++) {
            int l = path[i], r = path[i+1];
            for (int& e : edges[mp[{l, r}]].c) c.push_back(e);
        }
        sort(c.begin(), c.end());
        int cur = 0, mnd = sz(c);
        for (int i = 0; i < sz(c); i++) {
            cur += c[i];
            if (cur <= y) {
                int d = sz(c) - i - 1;
                mnd = min(mnd, d);
            }
        }
        if (x < mnd) {
            cout << "-1\n";
            goto bye;
        }
        cout << x - mnd << "\n";
        bye:{}
    }
}

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