Submission #1210193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210193		dima2101	Two Currencies (JOI23_currencies)	C++20	28 / 100	352 ms	50460 KiB

currencies

#include <bits/stdc++.h>
#define int long long

struct Node
{
    int stop;
    int was;
    Node(int stop, int was) : stop(stop), was(was) {};
    Node() = default;
};

const int MAXN = 1e5 + 1;
const int LOGN = 20;
int up[MAXN][LOGN];
int dp[MAXN][LOGN];
int h[MAXN];

void dfs(int v, std::vector<std::vector<Node>> &g, int pred = -1)
{
    if (pred == -1)
    {
        h[v] = 0;
    }
    else
    {
        h[v] = h[pred] + 1;
    }
    for (int i = 1; i < LOGN; i++)
    {
        up[v][i] = up[up[v][i - 1]][i - 1];
        dp[v][i] = dp[up[v][i - 1]][i - 1] + dp[v][i - 1];
    }
    for (auto u : g[v])
    {
        if (u.stop != pred)
        {
            up[u.stop][0] = v;
            dp[u.stop][0] = u.was;

            dfs(u.stop, g, v);
        }
    }
}

int LCA(int a, int b)
{
    if (h[a] > h[b])
    {
        std::swap(a, b);
    }
    int ans = 0;
    for (int i = LOGN - 1; i >= 0; i--)
    {
        if ((h[b] - h[a]) >= (1 << i))
        {
            ans += dp[b][i];
            b = up[b][i];
        }
    }
    // std::cout << a << ' ' << b << "djfs;l" << std::endl;
    if (a == b)
    {
        return ans;
    }

    for (int i = LOGN - 1; i >= 0; i--)
    {
        if (up[a][i] != up[b][i])
        {
            ans += dp[a][i];
            ans += dp[b][i];
            a = up[a][i];
            b = up[b][i];
        }
    }
    ans += dp[a][0];
    ans += dp[b][0];
    return ans;
}

signed
main()
{
    int n, m, q;
    std::cin >> n >> m >> q;

    std::vector<std::pair<int, int>> all(n - 1);
    for (int i = 0; i < n - 1; i++)
    {
        std::cin >> all[i].first >> all[i].second;
        all[i].first--, all[i].second--;
    }
    std::vector<int> is_bad(n - 1, 0);
    int cost = 0;
    for (int i = 0; i < m; i++)
    {
        int p, c;
        std::cin >> p >> c;
        cost = c;
        is_bad[--p]++;
    }
    std::vector<std::vector<Node>> g(n);
    for (int i = 0; i < n - 1; i++)
    {
        g[all[i].first].push_back(Node(all[i].second, is_bad[i]));
        g[all[i].second].push_back(Node(all[i].first, is_bad[i]));
    }

    up[0][0] = 0;
    dfs(0, g);

    while (q--)
    {
        int start, stop, x, y;
        std::cin >> start >> stop >> x >> y;
        start--, stop--;

        int cnt = LCA(start, stop);

        int can_take = y / cost;

        if (can_take >= cnt)
        {
            std::cout << x << std::endl;
            continue;
        }
        int delta = cnt - can_take;
        if (delta > x)
        {
            std::cout << -1 << std::endl;
        }
        else
        {
            std::cout << x - delta << std::endl;
        }
    }
}

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