제출 #1281864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281864		hynmj	Two Currencies (JOI23_currencies)	C++20	0 / 100	5 ms	572 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][20];
int cst[N][20];
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 < 22; p++)
    {
        for (int i = 1; i <= n; i++)
        {
            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;
        if ((binary & mask) != 0)
        {
            k = st[k][i];
            ans += cst[k][i];
        }
    }
}

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])
        {
            u = st[u][i];
            v = st[v][i];
            ans += cst[u][i] + cst[v][i];
        }
    }
    ans += st[u][0] + st[v][0];
    return st[u][0];
}

int lca(int u, int v)
{
    if (dist[u] > dist[v])
        swap(u, v);
    int diff = dist[v] - dist[u];
    go_up(v, diff);
    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);
        edges.push_back({u, v});
    }
    dfs(1, 0);
    preprocess(n);
    int cost;
    for (int i = 0; i < m; i++)
    {
        int p, c;
        cin >> p >> c;
        p--;
        if (st[edges[p].first][0] == edges[p].second)
            cst[edges[p].first][0] = 1;
        else 
            cst[edges[p].second][0] = 1;
        cost = c;
    }
    int starting, ending, silver, gold;
    for (int i = 0; i < q; i++)
    {
        cin >> starting >> ending >> silver >> gold;
        lca(starting, ending);
        int can_buy = silver / cost;
        // use gold for the remiaining
        int gold_buy = max(0ll, ans - can_buy);
        gold_buy = min(gold_buy, gold);
        if (can_buy + gold_buy < ans)
            cout << -1;
        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: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32