Submission #792814

#	Time	Username	Problem	Language	Result	Execution time	Memory
792814		vjudge1	Two Currencies (JOI23_currencies)	C++17	38 / 100	239 ms	47620 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 = 0;

    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];

ll n, m, q, cnt[N][LOGN], depth[N], up[N][LOGN], P_C[N], pr_c = -1;

void dfs1(int v, int p) {
    depth[v] = depth[p] + 1;
    up[v][0] = p;
    for(int i = 1; i < LOGN; ++ i) {
        cnt[v][i] = cnt[v][i - 1] + cnt[ up[v][i - 1] ][i - 1];
        up[v][i] = up[ up[v][i - 1] ][i - 1];
    }
    for(auto &[u, w] : adj[v]) {
        if(u != p) {
            P_C[u] = w;
            cnt[u][0] = C[w].size();
            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;
}

ll fast_LCA(ll a, ll b) {
    ll c = 0;
    if(depth[a] < depth[b]) {
        swap(a, b);
    }
    for(int t = LOGN; t --> 0;) {
        if(depth[up[a][t]] >= depth[b]) {
            c += cnt[a][t];
            a = up[a][t];
        }
    }
    if(a == b) {
        return c;
    }
    for(int t = LOGN; t --> 0;) {
        if(up[a][t] != up[b][t]) {
            c += cnt[a][t];
            c += cnt[b][t];
            a = up[a][t];
            b = up[b][t];
        }
    }
    c += cnt[a][0];
    c += cnt[b][0];
    return 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';
    }   
}

void solve_subtask_2() {
    ll s, t, X, Y, Z;
    dfs1(1, 1);
    for(; q --> 0;) {
        cin >> s >> t >> X >> Y;
        Z = fast_LCA(s, t);
        Z -= Y / pr_c;
        cout << (X < Z ? -1 : X - max(0ll, 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});
    }
    bool subtsk2 = true;
    for(int p, c; m --> 0;) {
        cin >> p >> c;
        if(pr_c != -1) {
            subtsk2 &= pr_c == c;
        }
        C[p].push_back(c);
        pr_c = c;
    }
    if(subtsk2) {
        solve_subtask_2();
        return 0;
    }
    if(n <= 2023 && q <= 2023) {
        solve_subtask_1();
        return 0;
    }
}

Compilation message (stderr)

currencies.cpp:125:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  125 | main() {
      | ^~~~

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