Submission #1262018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262018		M_W_13	Two Currencies (JOI23_currencies)	C++20	100 / 100	3891 ms	41812 KiB

currencies

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
const int MAXN = 1 << 17;
const int MAXK = 20;
int n, m, q;
int skok[MAXN][MAXK];
int depth[MAXN];
int pot[MAXK];
ll pom[MAXN];
bool czy[MAXN];
vector<pair<int, ll>> jakie[MAXN];
ll liczba[MAXN];
ll ile[MAXN];
int policz[MAXN];
int ans[MAXN];
int lastans[MAXN];
int preorder[MAXN];
int postorder[MAXN];
vector<int> graf[MAXN];
pair<ll, ll> monety[MAXN];
vector<pair<pair<int, int>, ll>> vec;
int kt = 1;
int kt2 = 1;
int uz = 0;

struct trojka {
    int a, b, c;
};

trojka pyt[MAXN];

void dfs(int v, int last) {
    preorder[v] = kt;
    kt++;
    depth[v] = depth[last] + 1;
    skok[v][0] = last;
    for (int k = 1; k < MAXK; k++) {
        skok[v][k] = skok[skok[v][k - 1]][k - 1];
    }
    for (auto w: graf[v]) {
        if (w == last) continue;
        dfs(w, v);
    }
    postorder[v] = kt2;
    kt2++;
}

int lca(int a, int b) {
    if (depth[a] > depth[b]) {
        swap(a, b);
    }
    int k = MAXK - 1;
    while (depth[a] != depth[b]) {
        if ((depth[b] - pot[k]) >= depth[a]) {
            b = skok[b][k];
        }
        k--;
    }
    if (a == b) {
        return a;
    }
    k = MAXK - 1;
    while (skok[a][0] != skok[b][0]) {
        if (skok[a][k] != skok[b][k]) {
            a = skok[a][k];
            b = skok[b][k];
        }
        k--;
    }
    return skok[a][0];
}

void dfs2(int v, int last, ll val, int val2) {
    val += pom[v];
    val2 += policz[v];
    // cout << "v = " << v << '\n';
    for (auto p: jakie[v]) {
        // cout << "nr = " << p.st << " ile = " << p.nd << '\n';
        ile[p.st] += (val * p.nd);
        ans[p.st] += (val2 * p.nd);
    }
    for (auto syn: graf[v]) {
        if (syn == last) continue;
        dfs2(syn, v, val, val2);
    }
}

bool czyojc(int a, int b) {
    if (preorder[a] <= preorder[b] && postorder[a] >= postorder[b]) {
        return true;
    }
    return false;
}

void zrob() {
    dfs2(1, 1, 0ll, 0);
    rep(i, q) {
        if (czy[i]) continue;
        // cout << "liczba = " << liczba[i] << " ile = " << ile[i] << '\n';
        if (ile[i] >= liczba[i]) {
            // cout << "i = " << i << endl;
            czy[i] = true;
            int it = 0;
            int t = 0;
            while (liczba[i] > 0) {
                int x = vec[it].st.st;
                int y = vec[it].st.nd;
                ll lic = vec[it].nd;
                // cout << "x = " << x << " y = " << y << " lic = " << lic << '\n';
                if (czyojc(pyt[i].c, x) && (czyojc(y, pyt[i].a) || czyojc(y, pyt[i].b))) {
                    // cout << "TAK" << endl;
                    t++;
                    liczba[i] -= lic;
                }
                it++;
            }
            if (liczba[i] < 0) {
                t--;
            }
            // cout << "i = " << i << " t = " << t << '\n';
            ans[i] -= (lastans[i] + t);
        }
        else {
            liczba[i] -= ile[i];
        }
    }
    rep(i, q) {
        lastans[i] = ans[i];
        ile[i] = 0;
    }
    rep(i, n + 1) {
        pom[i] = 0;
        policz[i] = 0;
    }
    vec.clear();
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    pot[0] = 1;
    for (int k = 1; k < MAXK; k++) {
        pot[k] = pot[k - 1] * 2;
    }

    cin >> n >> m >> q;
    vector<pair<int, int>> kraw;
    int sqr = 330;
    rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        graf[a].pb(b);
        graf[b].pb(a);
        kraw.pb({a, b});
    }
    dfs(1, 1);
    vector<pair<ll, int>> checks;
    rep(i, m) {
        int p;
        ll c;
        cin >> p >> c;
        p--;
        checks.pb({c, p});
    }
    rep(i, q) {
        int a, b;
        ll x, y;
        cin >> a >> b >> x >> y;
        monety[i] = {x, y};
        liczba[i] = y;
        int c = lca(a, b);
        pyt[i] = {a, b, c};
        jakie[a].pb({i, 1});
        jakie[b].pb({i, 1});
        jakie[c].pb({i, -2});
    }
    sort(checks.begin(), checks.end());
    for (auto p: checks) {
        int x = kraw[p.nd].st;
        int y = kraw[p.nd].nd;
        if (czyojc(y, x)) {
            swap(x, y);
        }
        vec.pb({{x, y}, p.st});
        policz[y]++;
        pom[y] += p.st;
        int sz = vec.size();
        if (sz >= sqr) {
            zrob();
        }
    }
    zrob();
    rep(i, q) {
        if (!czy[i]) {
            ans[i] = 0;
        }
        ll odp = monety[i].st - (long long)ans[i];
        if (odp < 0) {
            cout << -1 << '\n';
        }
        else {
            cout << odp << '\n';
        }
    }
    return 0;
}

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