Submission #928762

#	Time	Username	Problem	Language	Result	Execution time	Memory
928762		juliany2	Two Currencies (JOI23_currencies)	C++17	38 / 100	231 ms	41196 KiB

currencies

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 2e5 + 7, L = 20;
int n, m, q;
vector<int> adj[N], a[N];
array<int, 2> e[N];
int lift[N][L];
int dep[N];
ll w[N];

void dfs(int v = 1, int p = 0) {
    lift[v][0] = p;
    for (int i = 1; i < L; i++)
        lift[v][i] = lift[lift[v][i - 1]][i - 1];

    for (int u : adj[v]) {
        if (u == p)
            continue;

        dep[u] = dep[v] + 1;
        w[u] += w[v];
        dfs(u, v);
    }
}

int lca(int u, int v) {
    if (dep[u] > dep[v])
        swap(u, v);

    for (int i = L - 1; ~i; --i)
        if (dep[v] - (1 << i) >= dep[u])
            v = lift[v][i];

    if (u == v)
        return u;

    for (int i = L - 1; ~i; --i)
        if (lift[v][i] != lift[u][i])
            v = lift[v][i], u = lift[u][i];
    return lift[u][0];
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> m >> q;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
        e[i] = {u, v};
    }

    dfs();

    for (int i = 1; i < n; i++)
        if (dep[e[i][0]] < dep[e[i][1]])
            swap(e[i][0], e[i][1]);

    int costs;
    for (int i = 1; i <= m; i++) {
        int p, c;
        cin >> p >> c;

        w[e[p][0]]++;
        a[e[p][0]].push_back(c);
        costs = c;
    }

    dfs();

    while (q--) {
        ll s, t, y, c;
        cin >> s >> t >> y >> c;

        int l = lca(s, t);

        if (n <= 2000 && m <= 2000) {
            vector<int> weights;
            while (s != l) {
                for (int x : a[s])
                    weights.push_back(x);
                s = lift[s][0];
            }
            while (t != l) {
                for (int x : a[t])
                    weights.push_back(x);
                t = lift[t][0];
            }

            sort(all(weights));

            for (int x : weights) {
                if (c >= x)
                    c -= x;
                else
                    y--;
            }
        }
        else {
            int cnt = w[s] + w[t] - 2 * w[l];
            int take = min((ll) cnt, c / costs);

            y -= cnt - take;
        }

        cout << (y < 0 ? -1 : y) << '\n';
    }

    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:108:42: warning: 'costs' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |             int take = min((ll) cnt, c / costs);
      |                                          ^~~~~

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