Submission #856983

#	Time	Username	Problem	Language	Result	Execution time	Memory
856983		tvgk	Two Currencies (JOI23_currencies)	C++17	0 / 100	352 ms	223760 KiB

currencies

#include<bits/stdc++.h>
using namespace std;
#define task ""
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e5 + 7;

#define int long long

ll lg, n, m, Time[mxN], source, dd[mxN], par[mxN][30], root, h[mxN], cnt, q, u[mxN], v[mxN], ticket;
ii cost[mxN];
vector<int> w[mxN], sta[mxN];
struct T
{
    ll lt, rt, num, gt;
};
vector<T> tree[mxN * 4];

void Buildlog(int j)
{
    lg = log2(h[j]);
    for (int i = 1; i <= lg; i++)
        par[j][i] = par[par[j][i - 1]][i - 1];
}

void Build(int j, int height)
{
    dd[j] = 1;
    h[j] = height + 1;
    Buildlog(j);

    for (int i : w[j])
    {
        if (dd[i])
            continue;

        par[i][0] = j;
        Build(i, h[j]);
    }
}

int LCA(int u, int v)
{
    if (h[u] < h[v])
        swap(u, v);

    lg = log2(h[u]);
    for (int i = lg; i >= 0; i--)
    {
        if (h[par[u][i]] >= h[v])
            u = par[u][i];
    }

    if (u == v)
        return u;

    for (int i = lg; i >= 0; i--)
    {
        if (par[u][i] != par[v][i])
        {
            u = par[u][i];
            v = par[v][i];
        }
    }

    return par[u][0];
}

T change(ll gt, int lt, int rt, int num)
{
    T tmp;
    tmp.num = num;
    tmp.gt = gt;
    tmp.lt = lt;
    tmp.rt = rt;
    return tmp;
}

void Update(int j, int l, int r, int p, int Time)
{
    if (l == r)
    {
        tree[j].push_back(change(cost[l].fi, 0, 0, 1));
        return;
    }

    tree[j].push_back(tree[j][Time]);
    tree[j].back().num++;
    tree[j].back().gt += cost[p].fi;

    int mid = (l + r) / 2;
    if (p <= mid)
    {
        Update(j * 2, l, mid, p, tree[j][Time].lt);
        tree[j].back().lt = tree[j * 2].size() - 1;
    }
    else
    {
        Update(j * 2 + 1, mid + 1, r, p, tree[j][Time].rt);
        tree[j].back().rt = tree[j * 2 + 1].size() - 1;
    }
}

void Euler(int j, int k)
{
    dd[j] = 0;
    Time[j] = k;
    for (int i : sta[j])
    {
        Update(1, 1, m, i, Time[j]);
        Time[j] = tree[1].size() - 1;
    }

    for (int i : w[j])
    {
        if (!dd[i])
            continue;

        Euler(i, Time[j]);
    }
}

ll Get(int j, int l, int r, int cs1, int cs2, int cs3)
{
    ll tmp = tree[j][cs1].gt + tree[j][cs2].gt - tree[j][cs3].gt * 2;

    if (tmp <= source)
    {
        source -= tmp;
        return tree[j][cs1].num + tree[j][cs2].num - tree[j][cs3].num * 2;
    }

    if (cost[l].fi > source)
        return 0;
    if (l == r)
        return 0;

    int mid = (l + r) / 2;  
    return Get(j * 2, l, mid, tree[j][cs1].lt, tree[j][cs2].lt, tree[j][cs3].lt) + Get(j * 2 + 1, mid + 1, r, tree[j][cs1].rt, tree[j][cs2].rt, tree[j][cs3].rt);
}

ll vt;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        cin >> u[i] >> v[i];
        w[u[i]].push_back(v[i]);
        w[v[i]].push_back(u[i]);
    }
    Build(1, 0);

    for (int i = 1; i <= m; i++)
    {
        cin >> vt >> cost[i].fi;

        if (h[u[vt]] > h[v[vt]])
            swap(u[vt], v[vt]);
        cost[i].se = v[vt];
    }

    sort(cost + 1, cost + m + 1);
    for (int i = 1; i <= m; i++)
    {
        vt = cost[i].se;
        sta[vt].push_back(i);
    }

    for (int i = 1; i <= 4 * m; i++)
        tree[i].push_back(change(0, 0, 0, 0));
    Euler(1, 0);

    for (int i = 1; i <= q; i++)
    {
        cin >> u[0] >> v[0] >> ticket >> source;
        root = LCA(u[0], v[0]);

        ll tmp = ticket - (tree[1][Time[u[0]]].num + tree[1][Time[v[0]]].num - 2 * tree[1][Time[root]].num) + Get(1, 1, n, Time[u[0]], Time[v[0]], Time[root]);
        if (tmp < 0)
            cout << -1 << '\n';
        else
            cout << tmp << '\n';
    }
}

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