Submission #1281889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281889		hynmj	Two Currencies (JOI23_currencies)	C++20	28 / 100	368 ms	47704 KiB

currencies

#include <bits/stdc++.h>
#define int long long
using namespace std;
const long long N = 1e6 + 5;
int a[N];
int n, m, q, u, v;
// const int N = 2e5 + 3;
vector<int> graph[N];
int st[N][22];
int cst[N][22];
int dist[N];
int mask;
int ans = 0;

void dfs(int node, int parent)
{
    st[node][0] = parent;
    dist[node] = dist[parent] + 1;
    for (auto i : graph[node])
    {
        if (parent != i)
            dfs(i, node);
    }
}

void preprocess(int n)
{
    for (int p = 1; p < 21; p++)
    {
        for (int i = 1; i <= n; i++)
        {
            // cout << i << " " << p << endl;
            st[i][p] = st[st[i][p - 1]][p - 1];
            cst[i][p] = cst[i][p - 1] + cst[st[i][p - 1]][p - 1];
        }
    }
}

void go_up(int &k, int binary)
{

    for (int i = 0; i <= 20; i++)
    {
        mask = 1LL << i;
        // cout << cst[6][0] << endl;
        if ((binary & mask) != 0)
        {

            ans += cst[k][i];
            k = st[k][i];
            // cout << ans << endl;
        }
    }
}

int same_at_height(int u, int v)
{
    if (u == v)
        return v;
    for (int i = 18; i >= 0; i--)
    {
        if (st[u][i] != st[v][i])
        {
            ans += cst[u][i] + cst[v][i];
            u = st[u][i];
            v = st[v][i];
        }
    }
    ans += cst[u][0] + cst[v][0];
    // cout << " at " << u << " " << v << endl;
    // cout << ans << endl;
    return st[u][0];
}

int lca(int u, int v)
{
    if (dist[u] > dist[v])
        swap(u, v);
    int diff = dist[v] - dist[u];
    // cout << " at " << v << " going up " << u << endl;
    go_up(v, diff);

    // cout << " at " << u << " " << v << endl;
    // cout << ans << endl;

    if (u == v)
        return u;
    return same_at_height(u, v);
}
void solve()
{
    cin >> n >> m >> q;
    vector<pair<int, int>> edges;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        edges.push_back({u, v});
    }
    dfs(1, 0);
    int cost;
    // for (int i = 0; i < n; i++)
    // {
    // cout << st[i][0] << " ";
    // }
    // cout << endl;
    for (int i = 0; i < m; i++)
    {
        int p, c;
        cin >> p >> c;
        p--;
        if (dist[edges[p].first] > dist[edges[p].second])
        {

            cst[edges[p].first][0] += 1;
            // cout << edges[p].first << " " << cst[edges[p].first][0];
        }
        else
        {
            cst[edges[p].second][0] += 1;
            // cout << edges[p].second << " " << cst[edges[p].second][0] << endl;
        }
        // cout << endl;
        cost = c;
    }
    // cout << "done" << endl;
    // for (int i = 0; i < n; i++)
    // {
    //     cout << cst[i][0] << " ";
    // }
    preprocess(n + 1);
    // cout << endl;
    // for (int i = 0; i < n; i++)
    // {
    //     cout << st[i][0] << " ";
    // }
    // cout << endl;
    // cout << st[8][0] << endl;
    // cout << cst[9][2] << endl;
    int starting, ending, silver, gold;
    for (int i = 0; i < q; i++)
    {
        cin >> starting >> ending >> gold >> silver;
        ans = 0;
        lca(starting, ending);
        int can_buy = silver / cost;
        // use gold for the remiaining
        int gold_buy = max(0ll, ans - can_buy);
        // cout << ans << endl;
        gold_buy = min(gold_buy, gold);
        if (can_buy + gold_buy < ans)
            cout << -1 << endl;
        else
            cout << gold - gold_buy << endl;
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
        // cout << "Case #" << i << ':' << ' ';
        solve();
        cout << endl;
    }
    return 0;
}

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