Submission #792752

#	Time	Username	Problem	Language	Result	Execution time	Memory
792752		vjudge1	Two Currencies (JOI23_currencies)	C++17	0 / 100	2 ms	4948 KiB

currencies

#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 100100;
const int LOGN = 17;

struct MyPQ{
    priority_queue < int > pq;
    ll sum = 0, y, c;

    MyPQ(ll y):y(y) {};

    void add(ll x) {
        pq.push(x);
        sum += x;
        for(; sum > y;) {
            sum -= pq.top();
            pq.pop();
            ++ c;
        }
    }
};

vector < pair < int, int > > adj[N];
vector < int > C[N];

int n, m, q, cnt[N][LOGN], depth[N], up[N][LOGN], P_C[N];

void dfs1(int v, int p) {
    depth[v] = depth[p] + 1;
    up[v][0] = p;
    for(int i = 1; i < LOGN; ++ i) {
        up[v][i] = up[ up[v][i - 1] ][i - 1];
    }
    for(auto &[u, w] : adj[v]) {
        if(u != p) {
            P_C[u] = w;
            dfs1(u, v);
        }
    }
}

ll slow_LCA(ll a, ll b, ll &Y) {
    if(depth[a] < depth[b]) {
        swap(a, b);
    }
    MyPQ ans(Y);
    for(; depth[a] > depth[b];) {
        for(auto &i : C[P_C[a]]) {
            ans.add(i);
        }
        a = up[a][0];
    }
    for(; a != b;) {
        for(auto &i : C[P_C[a]]) {
            ans.add(i);
        }
        for(auto &i : C[P_C[b]]) {
            ans.add(i);
        }
        a = up[a][0];
        b = up[b][0];
    }
    return ans.c;
}

void solve_subtask_1() {
    dfs1(1, 1);
    ll s, t, X, Y, Z;
    for(; q --> 0;) {
        cin >> s >> t >> X >> Y;
        Z = slow_LCA(s, t, Y);
        cout << (X < Z ? -1 : X - Z) << '\n';
    }   
}

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> q;
    for(int u, v, i = 1; i < n; ++ i) {
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    for(int p, c; m --> 0;) {
        cin >> p >> c;
        C[p].push_back(c);
    }
    if(n <= 2023 && q <= 2023) {
        solve_subtask_1();
        return 0;
    }
}

Compilation message (stderr)

currencies.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   85 | main() {
      | ^~~~
currencies.cpp: In function 'll slow_LCA(ll, ll, ll&)':
currencies.cpp:72:16: warning: 'ans.MyPQ::c' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |     return ans.c;
      |                ^

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