Submission #1262281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262281		anteknne	Two Currencies (JOI23_currencies)	C++20	100 / 100	3267 ms	65852 KiB

currencies

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<ll, ll>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

struct el {
    ll a;
    ll b;
    ll x;
    ll y;
};

const ll MAXN = 100 * 1000 + 17;
const ll MAXQ = 100 * 1000 + 17;
const ll MAXLOG = 20;
const ll K = 20;
vector<ll> graf[MAXN];
ll pre[MAXN];
ll post[MAXN];
ll st[8 * MAXN];
vector<pair<ll, ll>> bram;
ll tp[MAXQ];
ll tk[MAXQ];
ll tsr[MAXQ];
bool tok[MAXQ];
ll tw[MAXQ];
el zap[MAXQ];
vector<ll> jakie[MAXN];
vector<pii> kraw;
ll pam[MAXN][MAXLOG];
ll lev[MAXN];
ll wyn[MAXQ];

ll cnt = 0;
void DFS (ll v, ll o) {
    pre[v] = cnt;
    cnt ++;
    for (auto x : graf[v]) {
        if (x != o) {
            DFS(x, v);
        }
    }
    post[v] = cnt;
    cnt ++;
}

void aktualizuj(ll p, ll k, ll a, ll b, ll w, ll i) {
    if (p > b || k < a) {
        return;
    }
    if (a <= p && k <= b) {
        st[i] += w;
        return;
    }
    ll sr = (p + k)/2;
    aktualizuj(p, sr, a, b, w, i * 2);
    aktualizuj(sr + 1, k, a, b, w, i * 2 + 1);
}

ll zapytanie(ll p, ll k, ll ind, ll i) {
    if (p == k && k == ind) {
        return st[i];
    }
    ll sr = (p + k)/2;
    ll a = 0;
    if (ind <= sr) {
        a = zapytanie(p, sr, ind, i * 2);
    } else {
        a = zapytanie(sr + 1, k, ind, i * 2 + 1);
    }
    return (a + st[i]);
}


void DFS2(ll v, ll p) {
    pam[v][0] = p;
    for (ll i = 1; i < MAXLOG; i ++) {
        pam[v][i] = pam[pam[v][i - 1]][i - 1];
    }
    for (auto x : graf[v]) {
        if (x != p) {
            lev[x] = lev[v] + 1;
            DFS2(x, v);
        }
    }
}

ll LCA(ll a, ll b) {
    if (lev[a] < lev[b]) {
        swap(a, b);
    }
    ll pot = (1 << (MAXLOG - 1));
    for (ll i = MAXLOG - 1; i >= 0; i--) {
        if (lev[a] - pot >= lev[b]) {
            a = pam[a][i];
        }
        pot /= 2;
    }
    if (a == b) {
        return a;
    }

    for (ll i = MAXLOG - 1; i >= 0; i--) {
        if (pam[a][i] != pam[b][i]) {
            a = pam[a][i];
            b = pam[b][i];
        }
    }
    return pam[a][0];
}

bool comp (pii a, pii b) {
    return (a.nd < b.nd);
}

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ll n, m, q;
    cin >> n >> m >> q;

    ll a, b;
    kraw.pb({0, 0});
    for (ll i = 0; i < n - 1; i ++) {
        cin >> a >> b;
        graf[a].pb(b);
        graf[b].pb(a);
        kraw.pb({a, b});
    }

    ll p;
    ll c;
    bram.pb({0, 0});
    for (ll i = 1; i <= m; i ++) {
        cin >> p >> c;
        bram.pb({p, c});
    }

    sort(bram.begin(), bram.end(), comp);
    for (auto x : bram) {
        //cout << x.nd << "\n";
    }

    for (ll i = 0; i < q; i ++) {
        cin >> zap[i].a >> zap[i].b >> zap[i].x >> zap[i].y;
    }

    DFS(1, 1);
    DFS2(1, 1);

    //cout << LCA(3, 5) << "\n";

    ll nr = 0;
    for (auto x : kraw) {
        if (pre[x.nd] > pre[x.st]) {
            swap(kraw[nr].st, kraw[nr].nd);
        }
        nr ++;
    }

    for (ll i = 0; i < q; i ++) {
        tk[i] = m;
    }

    for (ll zz = 0; zz < K; zz ++) {
        for (ll i = 0; i <= m; i ++) {
            jakie[i].clear();
        }

        for (ll i = 0; i < q; i ++) {
            tok[i] = false;
            tsr[i] = (tp[i] + tk[i])/ 2;
            if (tp[i] <= tk[i]) {
                jakie[tsr[i]].pb(i);
            } else {
                tsr[i] = tw[i];
            }

        }

        for (ll i = 0; i <= m; i ++) {
            ll v = kraw[bram[i].st].st;
            //cout << i << ": " << v << "\n";
            if (i != 0) {
                aktualizuj(0, 2 * n, pre[v], post[v], bram[i].nd, 1);
            }

            for (auto x : jakie[i]) {
                ll s1 = zapytanie(0, 2 * n, pre[zap[x].a], 1);
                ll s2 = zapytanie(0, 2 * n, pre[zap[x].b], 1);
                ll s3 = zapytanie(0, 2 * n, pre[LCA(zap[x].b, zap[x].a)], 1);
                //cout << x << "\n";
                //cout << i << " " << s1 << " " << s2 << " " << s3 << "\n";
                //cout << tw[x] << "\n";
                //cout << s1 + s2 - 2LL * s3 << "?" << zap[x].y << "\n";
                if ((s1 + s2 - 2LL * s3) <= zap[x].y) {
                    tok[x] = true;
                    //cout << "ha\n";
                }
                //cout << tok[x] << "\n";
                //cout << "\n";
            }
        }

        for (ll i = 0; i < q; i ++) {
            if (tp[i] <= tk[i]) {
                if (tok[i]) {
                    tw[i] = tsr[i];
                    tp[i] = tsr[i] + 1;
                } else {
                    tk[i] = tsr[i] - 1;
                }
            }
        }

        for (ll i = 0; i < 8 * n; i ++) {
            st[i] = 0;
        }
    }

    //cout << tw[0] << "\n";

    for (ll i = 0; i <= m + 1; i ++) {
        jakie[i].clear();
    }

    for (ll i = 0; i < q; i ++) {
        jakie[tw[i] + 1].pb(i);
    }

    for (ll i = m + 1; i >= 1; i --) {
        if (i != m + 1) {
            ll v = kraw[bram[i].st].st;
            aktualizuj(0, 2 * n, pre[v], post[v], 1, 1);
        }
        for (auto x : jakie[i]) {
            ll s1 = zapytanie(0, 2 * n, pre[zap[x].a], 1);
            ll s2 = zapytanie(0, 2 * n, pre[zap[x].b], 1);
            ll s3 = zapytanie(0, 2 * n, pre[LCA(zap[x].b, zap[x].a)], 1);
            wyn[x] = max(-1LL, zap[x].x - (s1 + s2 - 2LL * s3));
        }
    }

    for (ll i = 0; i < q; i ++) {
        cout << wyn[i] << "\n";
    }

    return 0;
}

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