Submission #1262069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262069		niepamietamhasla	Two Currencies (JOI23_currencies)	C++20	100 / 100	942 ms	171076 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<ll,ll>

const ll MAXN = 1e5 + 5;
const ll INF = 2e12;

map<ll,ll> scal;
map<ll,ll> wtyl;
ll cnt = 1;

struct Node{
    ll suma;
    ll ilosc;

    Node *l, *r;
    Node(ll x, ll y) : suma(x), ilosc(y) {};
    Node(Node *ll, Node *rr) : suma(ll->suma + rr->suma), ilosc(ll->ilosc + rr->ilosc), l(ll), r(rr) {};
};

vector<pair<ll, vector<ll>>> graf[MAXN];
ll gl[MAXN];
ll ile[MAXN];
ll przodek[MAXN][17];


Node *roots[MAXN];

struct d{
    ll a;
    ll b;
    vector<ll> koszty;
};

vector<d> kraw;

const ll base = 1 << 17;

Node *build(ll akt_a = 1, ll akt_b = base){
    if(akt_a == akt_b) return new Node(0ll, 0ll);
    ll mid = (akt_a + akt_b) / 2;
    return new Node(build(akt_a, mid), build(mid + 1, akt_b));
}

Node *dodaj(Node *w, ll ind, ll akt_a = 1, ll akt_b = base){
    if(akt_a == akt_b){
        return new Node(w->suma + wtyl[ind], w->ilosc + 1);
    }
    ll mid = (akt_a + akt_b) / 2;
    if(ind <= mid){
        return new Node(dodaj(w->l, ind, akt_a, mid), w->r);
    }
    else{
        return new Node(w->l, dodaj(w->r, ind, mid + 1, akt_b));
    }
}

set<ll> koszty;

ll ktory[MAXN];

ll it = 2;

void dfs(ll v, ll p){
    for(auto u : graf[v]){
        if(u.first == p) continue;
        gl[u.first] = gl[v] + 1;
        przodek[u.first][0] = v;
        ile[u.first] = ile[v] + u.second.size();
        for(ll j = 1; j < 17; ++j){
            przodek[u.first][j] = przodek[przodek[u.first][j-1]][j-1];
        }
        if(u.second.size() == 0) ktory[u.first] = ktory[v];
        for(ll j = 0; j < u.second.size(); ++j){
            if(j == 0){
                roots[it] = dodaj(roots[ktory[v]], u.second[j], 1, base);
                ktory[u.first] = it;
                ++it;
            }
            else{
                roots[it] = dodaj(roots[ktory[u.first]], u.second[j], 1, base);
                ktory[u.first] = it;
                ++it;
            }
        }
        dfs(u.first, v);
    }
}

ll LCA(ll x, ll y){
    if(x == y) return x;
    if(gl[x] < gl[y]) swap(x, y);
    for(ll j = 16; j >= 0; --j){
        if(gl[x] - (1 << j) >= gl[y]){
            x = przodek[x][j];
        }
    }
    if(x == y) return x;
    for(ll j = 16; j >= 0; --j){
        if(gl[x] >= (1 << j) and przodek[x][j] != przodek[y][j]){
            x = przodek[x][j];
            y = przodek[y][j];
        }
    }
    return przodek[x][0];
}

ll obl(Node *a, Node *b, Node *x, ll suma, ll akt_a, ll akt_b, ll currsuma){
    if(akt_a == akt_b){
        ll S = a->suma + b->suma - 2 * x->suma;
        ll L = a->ilosc + b->ilosc - 2 * x->ilosc;
        if(S == 0 or L == 0) return 0;
        else return min(L, (suma - currsuma) / (S / L));
    }
    ll mid = (akt_a + akt_b) / 2;
    ll lewasuma = a->l->suma + b->l->suma - 2 * x->l->suma;
    ll lewailosc = a->l->ilosc + b->l->ilosc - 2 * x->l->ilosc;
    if(currsuma + lewasuma < suma){
        return obl(a->r, b->r, x->r, suma, mid + 1, akt_b, currsuma + lewasuma) + lewailosc;
    }
    else{
        return obl(a->l, b->l, x->l, suma, akt_a, mid, currsuma);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, m, q;
    cin >> n >> m >> q;
    ll a, b;
    for(ll i = 0; i < n-1; ++i){
        cin >> a >> b;
        kraw.push_back({a, b});
    }
    for(ll i = 0; i < m; ++i){
        cin >> a >> b;
        kraw[a-1].koszty.push_back(b);
        koszty.insert(b);
    }
    for(auto u : koszty){
        scal[u] = cnt;
        wtyl[cnt] = u;
        ++cnt;
    }
    for(auto &u : kraw){
        graf[u.a].push_back({u.b, {}});
        graf[u.b].push_back({u.a, {}});
        for(auto &t : u.koszty){
            t = scal[t];
            graf[u.a].back().second.push_back(t);
            graf[u.b].back().second.push_back(t);
        }
    }
    roots[1] = build();
    ktory[1] = 1;
    dfs(1, 0);
    ll c, d;
    for(ll i = 0; i < q; ++i){
        cin >> a >> b >> c >> d;
        ll x = LCA(a, b);
        ll ans = c - (ile[a] + ile[b] - 2 * ile[x] - obl(roots[ktory[a]], roots[ktory[b]], roots[ktory[x]], d, 1, base, 0));
        if(ans < 0) cout << -1 << "\n";
        else cout << ans << "\n";
    }
    return 0;
}

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