Submission #1210270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210270		jerzyk	Two Currencies (JOI23_currencies)	C++20	0 / 100	5 ms	5448 KiB

currencies

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const int II = 1'000'000'000;
const ll I = 1'000'000'000'000'000'000LL;
const int K = 17;
const int N = 1<<K;

pair<int, int> e[N];
vector<int> ed[N];
int jp[K + 1][20];
int pos[N], pre[N], cnt = 0;

ll drz[2 * N];

pair<ll, ll> il[N];
int v1[N], v2[N], l[N];
int poc[N], kon[N];
ll akt[N];
pair<int, int> que[N];

pair<int, int> dod[N];

ll answer[N];

void Add(int a, int b, ll x)
{
    a += N - 1; b += N + 1;
    while(a / 2 != b / 2)
    {
        if(a % 2 == 0) drz[a + 1] += x;
        if(b % 2 == 1) drz[b - 1] += x;
        a /= 2; b /= 2;
    }
}

ll Sum(int v)
{
    ll ans = 0LL;
    v += N;
    while(v > 0)
    {
        ans += drz[v];
        v /= 2;
    }
    return ans;
}

void DFS(int v)
{
    ++cnt; pre[v] = cnt; pos[v] = cnt;
    for(int i = 1; i <= K; ++i)
        jp[v][i] = jp[jp[v][i - 1]][i - 1];
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(pre[ed[v][i]]) continue;
        jp[ed[v][i]][0] = v;
        DFS(ed[v][i]);
        pos[v] = pos[ed[v][i]];
    }
}

int LCA(int a, int b)
{
    if(pre[a] > pre[b]) swap(a, b);
    for(int i = K; i >= 0; --i)
        if(pos[jp[a][i]] < pre[b]) a = jp[a][i];
    if(pos[a] < pre[b]) a = jp[a][0];
    return a;
}

void Check(int m, int q, bool r)
{
    for(int i = 1; i < 2 * N; ++i) drz[i] = 0;
    int j = 0;
    sort(que + 1, que + 1 + q);
    for(int i = 1; i <= q; ++i)
    {
        while(j < m && dod[j + 1].st <= que[i].st)
        {
            ++j;
            if(r)
                Add(pre[dod[j].nd], pos[dod[j].nd], dod[j].st);
            else
                Add(pre[dod[j].nd], pos[dod[j].nd], 1);
        }
        int a = que[i].nd;
        ll cur = Sum(pre[v1[a]]) + Sum(pre[v2[a]]) - 2LL * Sum(pre[l[a]]);
        akt[a] = cur;
    }
}

void BS(int m, int q)
{
    for(int i = 1; i <= q; ++i)
    {poc[i] = 0; kon[i] = II;}
    for(int xd = 1; xd <= 30; ++xd)
    {
        for(int i = 1; i <= q; ++i)
            que[i] = pair{(poc[i] + kon[i] + 1) / 2, i};
        Check(m, q, 1);
        for(int i = 1; i <= q; ++i)
        {
            int s = (poc[i] + kon[i] + 1) / 2;
            if(akt[i] > il[i].nd)
                kon[i] = s - 1;
            else
                poc[i] = s;
        }
    }
}

void DoAns(int m, int q)
{
    for(int i = 1; i <= q; ++i)
        que[i] = pair{poc[i], i};
    Check(m, q, 1);
    for(int i = 1; i <= q; ++i)
        answer[i] = (il[i].nd - akt[i]) / (ll)(poc[i] + 1);
    Check(m, q, 0);
    for(int i = 1; i <= q; ++i)
    {
        answer[i] += akt[i];
        que[i] = pair{II + 1, i};
    }
    Check(m, q, 0);
    for(int i = 1; i <= q; ++i)
    {
        answer[i] = il[i].st - akt[i] + answer[i];
        if(answer[i] < 0LL)
            answer[i] = -1LL;
    }
}

void Solve()
{
    int n, m, q, a, b;
    cin >> n >> m >> q;
    for(int i = 1; i < n; ++i)
    {
        cin >> a >> b;
        e[i] = pair{a, b};
        ed[a].pb(b); ed[b].pb(a);
    }
    jp[1][0] = 1;
    DFS(1);
    for(int i = 1; i <= m; ++i)
    {
        cin >> a >> b;
        if(jp[e[a].st][0] == e[a].nd)
            a = e[a].st;
        else
            a = e[a].nd;
        dod[i] = pair{b, a};
    }
    sort(dod + 1, dod + 1 + m);
    for(int i = 1; i <= q; ++i)
    {
        cin >> v1[i] >> v2[i] >> il[i].st >> il[i].nd;
        l[i] = LCA(v1[i], v2[i]);
    }
    BS(m, q);
    DoAns(m, q);
    for(int i = 1; i <= q; ++i)
        cout << answer[i] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
        Solve();

    return 0;
}

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