Submission #991500

#	Time	Username	Problem	Language	Result	Execution time	Memory
991500		KietJ	Two Currencies (JOI23_currencies)	C++17	10 / 100	134 ms	13396 KiB

currencies

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

#define f first
#define s second
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair <int, int> ii;

const int N = 2e5 + 1;
const int mod = 998244353;

int n, m, q;
int p[N], c[N], mark[N];
vector <int> path, save;
vector <ii> ed[N];

void dfs(int u, int par, int k) {
    if (u == k) 
        save = path;

    for(auto v: ed[u]) {
        if (v.f == par) continue;
        path.push_back(v.s);
        dfs(v.f, u, k);
        path.pop_back();
    }
}

void sub1() {
    while (q--) {
        int s, t, x; ll y; 
        cin >> s >> t >> x >> y;
        dfs(s, s, t);

        for(auto x: save)
            mark[x] = true;

        priority_queue <int, vector <int>, greater <int>> pq;

        for(int i = 1; i <= m; i++) {
            if (mark[p[i]]) {
                pq.push(c[i]);
            }
        }

        while (sz(pq) && y >= pq.top()) y -= pq.top(), pq.pop();

        cout << (x >= sz(pq) ? x - sz(pq) : -1) << "\n";

        for(auto x: save)
            mark[x] = false;
    }
}

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

    for(int i = 1; i <= m; i++) 
        cin >> p[i] >> c[i];

    if (n <= 2000 && m <= 2000 && q <= 2000) {
        sub1();
    }
    return 0;
}

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