Submission #1262269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262269		miniob	Two Currencies (JOI23_currencies)	C++20	100 / 100	1792 ms	45084 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

long long przod[100007][19];
long long gl[100007];
long long preord[100007];
long long prawk[100007];
long long ilemaxx[100007];
long long odp[100007];
long long n, m, q;
vector<long long> graph[100007];
vector<pair<long long, long long>> bramki;
long long t = 0;
long long drz[262150];
long long drz2[262150];

struct zapyt{
    long long ind, l, r, lca, s, t, x, y;
};

bool sfunkc(const zapyt& a, const zapyt& b)
{
    return ((a.l + a.r) / 2) < ((b.l + b.r) / 2);
}

void dfs(long long cur, long long pop)
{
    gl[cur] = gl[pop] + 1;
    preord[cur] = t;
    prawk[cur] = t;
    t++;
    if(pop != -1)
    {
        przod[cur][0] = pop;
    }
    for(auto x : graph[cur])
    {
        if(x != pop)
        {
            dfs(x, cur);
            prawk[cur] = max(prawk[cur], prawk[x]);
        }
    }
}

long long lca(long long a, long long b)
{
    if(gl[a] > gl[b])
    {
        swap(a, b);
    }
    for(long long i = 18; i >= 0; i--)
    {
        if(gl[przod[b][i]] >= gl[a])
        {
            b = przod[b][i];
        }
    }
    if(a == b)
    {
        return a;
    }
    for(long long i = 18; i >= 0; i--)
    {
        if(przod[a][i] != przod[b][i])
        {
            a = przod[a][i];
            b = przod[b][i];
        }
    }
    return przod[a][0];
}

void policzlca()
{
    przod[1][0] = 1;
    for(long long i = 1; i < 19; i++)
    {
        for(long long j = 1; j <= n; j++)
        {
            przod[j][i] = przod[przod[j][i - 1]][i - 1];
        }
    }
}

void dodaj(long long l, long long r, long long curl, long long curr, long long gdzie, long long ile)
{
    if(l > curr || r < curl)
    {
        return;
    }
    else if(l <= curl && curr <= r)
    {
        drz[gdzie] += ile;
    }
    else 
    {
        dodaj(l, r, curl, (curl + curr) / 2, 2 * gdzie, ile);
        dodaj(l, r, (curl + curr) / 2 + 1, curr, 2 * gdzie + 1, ile);
    }
}

long long sumap(long long gdzie)
{
    gdzie += 131072;
    long long suma = 0;
    while(gdzie != 0)
    {
        suma += drz[gdzie];
        gdzie /= 2;
    }
    return suma;
}

void dodaj2(long long l, long long r, long long curl, long long curr, long long gdzie, long long ile)
{
    if(l > curr || r < curl)
    {
        return;
    }
    else if(l <= curl && curr <= r)
    {
        drz2[gdzie] += ile;
    }
    else 
    {
        dodaj2(l, r, curl, (curl + curr) / 2, 2 * gdzie, ile);
        dodaj2(l, r, (curl + curr) / 2 + 1, curr, 2 * gdzie + 1, ile);
    }
}

long long sumap2(long long gdzie)
{
    gdzie += 131072;
    long long suma = 0;
    while(gdzie != 0)
    {
        suma += drz2[gdzie];
        gdzie /= 2;
    }
    return suma;
}

int main()
{
    cin >> n >> m >> q;
    vector<pair<long long, long long>> krawww;
    for(long long i = 0; i < n - 1; i++)
    {
        long long a, b;
        cin >> a >> b;
        krawww.push_back({a, b});
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(1, 0);
    policzlca();
    for(long long i = 0; i < m; i++)
    {
        long long p, c, gdzied;
        cin >> p >> c;
        if(gl[krawww[p - 1].first] > gl[krawww[p - 1].second])
        {
            gdzied = krawww[p - 1].first;
        }
        else
        {
            gdzied = krawww[p - 1].second;
        }
        bramki.push_back({c, gdzied});
    }
    sort(bramki.begin(), bramki.end());
    vector<zapyt> wszystkiezapyt;
    for(long long i = 0; i < q; i++)
    {
        long long s, t, x, y;
        cin >> s >> t >> x >> y;
        zapyt temp;
        temp.l = 0;
        temp.r = m;
        temp.ind = i;
        temp.lca = lca(s, t);
        temp.x = x;
        temp.y = y;
        temp.s = s;
        temp.t = t;
        wszystkiezapyt.push_back(temp);
    }
    for(long long iter = 0; iter < 30; iter++)
    {
        sort(wszystkiezapyt.begin(), wszystkiezapyt.end(), sfunkc);
        long long dulgp = 0;
        for(long long i = 0; i < q; i++)
        {
            while(dulgp < (wszystkiezapyt[i].l + wszystkiezapyt[i].r) / 2)
            {
                dodaj(preord[bramki[dulgp].second], prawk[bramki[dulgp].second], 0, 131071, 1, bramki[dulgp].first);
                dodaj2(preord[bramki[dulgp].second], prawk[bramki[dulgp].second], 0, 131071, 1, 1);
                dulgp++;
            }
            if(sumap(preord[wszystkiezapyt[i].s]) + sumap(preord[wszystkiezapyt[i].t]) - 2 * sumap(preord[wszystkiezapyt[i].lca]) > wszystkiezapyt[i].y)
            {
                wszystkiezapyt[i].r = (wszystkiezapyt[i].l + wszystkiezapyt[i].r) / 2;
            }
            else
            {
            	ilemaxx[wszystkiezapyt[i].ind] = sumap2(preord[wszystkiezapyt[i].s]) + sumap2(preord[wszystkiezapyt[i].t]) - 2 * sumap2(preord[wszystkiezapyt[i].lca]);
                wszystkiezapyt[i].l = (wszystkiezapyt[i].l + wszystkiezapyt[i].r) / 2 + 1;
            }
        }
        for(long long i = 0; i < 262147; i++)
        {
            drz[i] = 0;
            drz2[i] = 0;
        }
    }
    for(long long i = 0; i < m; i++)
    {
        dodaj(preord[bramki[i].second], prawk[bramki[i].second], 0, 131071, 1, 1);
    }
    for(long long i = 0; i < q; i++)
    {
        long long ilebram = sumap(preord[wszystkiezapyt[i].s]) + sumap(preord[wszystkiezapyt[i].t]) - 2 * sumap(preord[wszystkiezapyt[i].lca]);
        if(ilebram - ilemaxx[wszystkiezapyt[i].ind] - wszystkiezapyt[i].x <= 0)
        {
            odp[wszystkiezapyt[i].ind] = wszystkiezapyt[i].x - ilebram + ilemaxx[wszystkiezapyt[i].ind];
        }
        else
        {
        	odp[wszystkiezapyt[i].ind] = -1;
        }
    }
    for(long long i = 0; i < q; i++)
    {
        cout << odp[i] << endl;
    }
}

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