제출 #1253530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253530		tvgk	Two Currencies (JOI23_currencies)	C++20	100 / 100	2902 ms	50476 KiB

currencies

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

int n, m, q, par[mxN][25], h[mxN], cnt[mxN], l[mxN], r[mxN], mid[mxN], u[mxN], v[mxN], vt[mxN], gold[mxN], ans[mxN];
ll sum[mxN], silver[mxN];
ii Nen[mxN], tree[mxN * 4];
vector<ii> querry[mxN];
vector<int> w[mxN], sta[mxN];

void Build(int j)
{
    for (int i = 1; i < 20; i++)
        par[j][i] = par[par[j][i - 1]][i - 1];

    for (int i : w[j])
    {
        if (i == par[j][0])
            continue;

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

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

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

    if (u == v)
        return u;

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

// Cong 2 pair
ii Plus(ii u, ii v)
{
    u.fi += v.fi;
    u.se += v.se;
    return u;
}

void Upd(int vt, bool tt, int j = 1, int l = 1, int r = m)
{
    if (l > vt || vt > r)
        return;

    if (l == r)
    {
        //fi la so luong
        //se la chi phi
        tree[j].fi = tt;
        tree[j].se = tt * Nen[l].fi;
        return;
    }

    int mid = (l + r) / 2;
    Upd(vt, tt, j * 2, l, mid);
    Upd(vt, tt, j * 2 + 1, mid + 1, r);
    tree[j] = Plus(tree[j * 2], tree[j * 2 + 1]);
}

// lay tong nhung gia tri nho nhat be hon mid
ii Get(int vt, int j = 1, int l = 1, int r = m)
{
    if (vt < l)
        return {0, 0};

    if (r <= vt)
        return tree[j];

    int mid = (l + r) / 2;
    return Plus(Get(vt, j * 2, l, mid), Get(vt, j * 2 + 1, mid + 1, r));
}

void DFS(int j)
{
    for (int i : sta[j])
        Upd(vt[i], 1);

    for (ii i : querry[j])
    {
        if (l[i.fi] > r[i.fi])
            continue;

        ii tmp = Get(mid[i.fi]);
        sum[i.fi] += tmp.se * i.se;
        cnt[i.fi] += (tree[1].fi - tmp.fi) * i.se;
    }

    for (int i : w[j])
    {
        if (i == par[j][0])
            continue;

        DFS(i);
    }

    for (int i : sta[j])
        Upd(vt[i], 0);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //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);

    for (int i = 1; i <= m; i++)
    {
        int id, cost;
        cin >> id >> cost;

        if (u[id] != par[v[id]][0])
            swap(u[id], v[id]);

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

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

        l[i] = 0;
        r[i] = m;
        ans[i] = -1;

        querry[u].push_back({i, 1});
        querry[v].push_back({i, 1});
        querry[root].push_back({i, -2});
    }

    while (1)
    {
        bool tt = 0;
        for (int i = 1; i <= q; i++)
        {
            sum[i] = 0;
            cnt[i] = 0;
            tt |= (l[i] <= r[i]);
            mid[i] = (l[i] + r[i]) / 2;
        }

        if (!tt)
            break;

        DFS(1);

        for (int i = 1; i <= q; i++)
        {
            if (l[i] > r[i])
                continue;

            if (sum[i] > silver[i])
                r[i] = mid[i] - 1;
            else
            {
                l[i] = mid[i] + 1;
                ans[i] = gold[i] - cnt[i];
            }
        }
    }

    for (int i = 1; i <= q; i++)
        cout << max(-1, ans[i]) << '\n';
}

/*
8 7 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 4
3 7
2 10
5 2
4 1
4 4
5 6
7 1 5 55
*/

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