Submission #950807

#	Time	Username	Problem	Language	Result	Execution time	Memory
950807		m1dsho	Two Currencies (JOI23_currencies)	C++98	100 / 100	4567 ms	76392 KiB

currencies

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define int long long

using namespace std;
struct node {
    int s, t, x, y;
};
const int N = 2e5 + 2;
const int L = 20;
int dp[L][N];
int tin[N];
int sz[N];
int H[N];
int up[N];
pair<int, int> t[5 * N];
vector<int> g[N];

void dfs1(int u, int p) {
    sz[u] = 1;
    H[u] = H[p] + 1;
    dp[0][u] = p;
    for (int i = 1; i < L; i++) {
        dp[i][u] = dp[i - 1][dp[i - 1][u]];
    }
    for (auto v: g[u]) {
        if (v == p) continue;
        dfs1(v, u);
        sz[u] += sz[v];
    }
}

int time_now = 0;

void dfs2(int u, int p) {
    tin[u] = time_now++;
    for (int i = 1; i < g[u].size(); i++) {
        if (g[u][i] == p) continue;
        if (sz[g[u][i]] > sz[g[u][0]] or g[u][0] == p) swap(g[u][i], g[u][0]);
    }
    for (int i = 0; i < g[u].size(); i++) {
        if (g[u][i] == p) continue;
        if (i == 0)up[g[u][i]] = up[u];
        else up[g[u][i]] = g[u][i];
        dfs2(g[u][i], u);

    }
}

int LA(int u, int h) {
    for (int i = 0; i < L; i++) {
        if ((1 << i) & h) {
            h -= (1 << i);
            u = dp[i][u];
        }
    }
    return u;
}

int LCA(int u, int v) {
    int h1 = H[u], h2 = H[v];
    if (h1 > h2) {
        u = LA(u, h1 - h2);
    }
    if (h2 > h1) {
        v = LA(v, h2 - h1);
    }
    for (int i = L - 1; i > -1; i--) {
        if (dp[i][u] != dp[i][v]) {
            u = dp[i][u];
            v = dp[i][v];
        }
    }
    if (u == v) return u;
    return dp[0][u];
}

void upd(int ind, int l, int r, int id, pair<int, int> x) {
    if (l + 1 == r) {
        t[ind].first += x.first;
        t[ind].second += x.second;
        return;
    }
    int mid = (l + r) / 2;
    if (mid > id) {
        upd(ind * 2, l, mid, id, x);
    } else {
        upd(ind * 2 + 1, mid, r, id, x);
    }
    t[ind].first += x.first;
    t[ind].second += x.second;
}

pair<int, int> get(int ind, int l, int r, int ql, int qr) {
    if (l >= ql and r <= qr) {
        return t[ind];
    }
    if (l >= qr or r <= ql) {
        return {0, 0};
    }
    int mid = (l + r) / 2;
    pair<int, int> ans1 = get(ind * 2, l, mid, ql, qr);
    pair<int, int> ans2 = get(ind * 2 + 1, mid, r, ql, qr);
    return {ans1.first + ans2.first, ans1.second + ans2.second};
}

pair<int, int> bup(int u, int lca, int h) {
    int sm = 0, cnt = 0;
    while (H[up[u]] > H[lca]) {
        pair<int, int> o = get(1, 0, 1 << h, tin[up[u]], tin[u] + 1);
        sm += o.first, cnt += o.second;
        u = dp[0][up[u]];
    }
    pair<int, int> o = get(1, 0, 1 << h, tin[lca] + 1, tin[u] + 1);
    sm += o.first, cnt += o.second;
    return {sm, cnt};
}

int gt(int u, int v, int y, int h, int ans) {
    int lca = LCA(u, v);
    int sms = 0, cnts = 0;
    pair<int, int> o1 = bup(u, lca, h), o2 = bup(v, lca, h);
    sms = o1.first + o2.first;
    cnts += o1.second + o2.second;
    if (sms > y) return 1e9;
    return max(ans - cnts, 0LL);
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int>> pr;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
        pr.push_back({u, v});
    }
    vector<pair<int, int>> cst;
    for (int i = 0; i < m; i++) {
        int p, c;
        cin >> p >> c;
        p--;
        cst.push_back({p, c});
    }
    dfs1(0, 0);
    dfs2(0, 0);
    int h = 0;
    while (1 << (++h) <= time_now);
    vector<pair<int, int>> n_c;
    for (auto [id, c]: cst) {
        int u = pr[id].first, v = pr[id].second;
        if (tin[v] < tin[u]) swap(u, v);
        n_c.push_back({c, v});
    }
    vector<node> qus(q);
    for (int i = 0; i < q; i++) {
        int start, fin, x, y;
        cin >> start >> fin >> x >> y;
        start--, fin--;
        node nd;
        nd.s = start, nd.t = fin, nd.x = x, nd.y = y;
        qus[i] = nd;
    }
    n_c.push_back({-1e9, -1e9});
    std::sort(n_c.begin(), n_c.end());
    vector<pair<int, int>> bin_pow(q, {0, n_c.size()});
    vector<int> ans(q, 1e9);
    vector<vector<int>> upds(n_c.size());
    vector<int> szs(q);
    for (int i = 0; i < n_c.size(); i++) {
        if (i != 0)upd(1, 0, 1 << h, tin[n_c[i].second], {n_c[i].first, 1});
    }
    for (int i = 0; i < q; i++) {
        int u = qus[i].s, v = qus[i].t;
        int lca = LCA(u, v);
        szs[i] += bup(u, lca, h).second + bup(v, lca, h).second;
        ans[i] = szs[i];
    }
    for (int i = 0; i < n_c.size(); i++) {
        if (i != 0)upd(1, 0, 1 << h, tin[n_c[i].second], {-n_c[i].first, -1});
    }
    while (true) {
        bool check = false;
        upds.clear();
        upds.resize(n_c.size());
        for (int i = 0; i < q; i++) {
            if (bin_pow[i].first + 1 == bin_pow[i].second) continue;
            check = true;
            upds[(bin_pow[i].first + bin_pow[i].second) / 2].push_back(i);
        }
        if (!check) break;
        for (int i = 0; i < n_c.size(); i++) {
            if (i != 0) upd(1, 0, 1 << h, tin[n_c[i].second], {n_c[i].first, 1});
            for (auto ind: upds[i]) {
                int an = gt(qus[ind].s, qus[ind].t, qus[ind].y, h, szs[ind]);
                ans[ind] = min(ans[ind], an);
                if (an != 1e9) {
                    bin_pow[ind].first = i;
                } else {
                    bin_pow[ind].second = i;
                }
            }
        }
        for (int i = 0; i < n_c.size(); i++) {
            if (i != 0)upd(1, 0, 1 << h, tin[n_c[i].second], {-n_c[i].first, -1});
        }
    }
    for (int i = 0; i < q; i++) {
        cout << max(-1LL, qus[i].x - ans[i]) << '\n';
    }
}

Compilation message (stderr)

currencies.cpp: In function 'void dfs2(long long int, long long int)':
currencies.cpp:37:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i = 1; i < g[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
currencies.cpp:41:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < g[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:154:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  154 |     for (auto [id, c]: cst) {
      |               ^
currencies.cpp:174:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |     for (int i = 0; i < n_c.size(); i++) {
      |                     ~~^~~~~~~~~~~~
currencies.cpp:183:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |     for (int i = 0; i < n_c.size(); i++) {
      |                     ~~^~~~~~~~~~~~
currencies.cpp:196:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |         for (int i = 0; i < n_c.size(); i++) {
      |                         ~~^~~~~~~~~~~~
currencies.cpp:208:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  208 |         for (int i = 0; i < n_c.size(); i++) {
      |                         ~~^~~~~~~~~~~~

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