Submission #844157

#	Time	Username	Problem	Language	Result	Execution time	Memory
844157		Quadrilateral	Two Currencies (JOI23_currencies)	C++17	100 / 100	3812 ms	54652 KiB

currencies

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define MAX 100010
#define MIN first
#define MAXNUM second
using namespace std;
using ll = long long;

int n, m, q;
int par[20][MAX], depth[MAX], in[MAX], out[MAX];
int max_h;
int dstep[MAX];
vector<int> graph[MAX];
int i, j;

struct spt {
    ll s, e, val;
    bool operator<(const spt& x) { return val < x.val; }
};

struct qu {
    ll s, t, x, y;
};

vector<spt> v_spt;
vector<qu> v_q;
int l[MAX], r[MAX];
vector<pair<int, int>> arr;

void fastIO() {
    ios::sync_with_stdio(false); cin.tie(0);
}

//euler tour trick.
int i_ett, i_order;
void ETT(int curr, int dep) {
    dstep[curr] = ++i_order; in[curr] = ++i_ett; depth[curr] = dep;
    for (int next : graph[curr]) {
        if (in[next]) continue;
        par[0][next] = curr;
        ETT(next, dep + 1);
    }
    i_ett++;
    out[curr] = i_ett;
}

//get parent based on sparse table.
void getParent() {
    int tmp = n, cnt = 0;
    while (tmp > 1) { tmp >>= 1; cnt++; }
    max_h = cnt;
    for (int h = 1; h <= max_h; h++) {
        for (int x = 2; x <= n; x++) {
            if (par[h - 1][x]) { par[h][x] = par[h - 1][par[h - 1][x]]; }
        }
    }
}

int getLCA(int a, int b) {
    if (depth[a] != depth[b]) {
        if (depth[a] < depth[b]) { swap(a, b); }
        int diff = depth[a] - depth[b];
        for (j = 0; diff > 0; j++) {
            if (diff & 1) { a = par[j][a]; }
            diff >>= 1;
        }
    }

    if (a != b) {
        for (int k = max_h; k >= 0; k--) {
            if (par[k][a] != 0 && par[k][a] != par[k][b]) {
                a = par[k][a]; b = par[k][b];
            }
        }
        a = par[0][a];
    }
    return a;
}

ll tree_cpt[8 * MAX], tree_first[8 * MAX], tree_cnt[8 * MAX];

void update(ll tree[], int curr, int start, int end, int idx, ll val) {
    if (start == end) { tree[curr] += val; return; }
    int lidx = curr << 1, ridx = lidx | 1, mid = start + end >> 1;
    if (idx <= mid) { update(tree, lidx, start, mid, idx, val); }
    else { update(tree, ridx, mid + 1, end, idx, val); }
    tree[curr] = tree[lidx] + tree[ridx];
}

ll getSum(ll tree[], int curr, int start, int end, int t_start, int t_end) {
    if (end < t_start || t_end < start) { return 0; }
    if (t_start <= start && end <= t_end) { return tree[curr]; }
    int lidx = curr << 1, ridx = lidx | 1, mid = start + end >> 1;
    return getSum(tree, lidx, start, mid, t_start, t_end) + getSum(tree, ridx, mid + 1, end, t_start, t_end);
}

void reset(int start = 1, int end = i_ett, int curr = 1) {
    tree_cpt[curr] = tree_cnt[curr] = 0;
    if (start == end) { return; }
    int mid = start + end >> 1;
    reset(start, mid, curr << 1);
    reset(mid + 1, end, curr << 1 | 1);
}


int ret[MAX], sum_sp[MAX], sum_cnt[MAX];

void input() {
    cin >> n >> m >> q;
    arr.resize(n);

    int a, b;
    for (i = 1; i <= n - 1; i++) {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
        arr[i] = { min(a, b), max(a,b) };
    }
    for (i = 1; i <= m; i++) {
        cin >> a >> b;
        v_spt.push_back({ arr[a].MIN, arr[a].MAXNUM, b });
    }
    sort(v_spt.begin(), v_spt.end());
    v_q.resize(q);
    for (i = 0; i < q; i++) {
        cin >> v_q[i].s >> v_q[i].t >> v_q[i].x >> v_q[i].y;
    }
}

void solve() {
    for (i = 0; i < MAX; i++) { ret[i] = -1; }
    ETT(1, 0);
    getParent();

    //pbs
    for (i = 0; i < q; i++) { l[i] = -1, r[i] = m; }

    for (i = 0; i < m; i++) {
        int start = v_spt[i].s, end = v_spt[i].e;
        if (in[end] <= in[start] && in[start] <= out[end]) swap(start, end);
        update(tree_first, 1, 1, i_ett, in[end], 1);
        update(tree_first, 1, 1, i_ett, out[end], -1);
    }

    for (i = 0; i < q; i++) {
        int lca = getLCA(v_q[i].s, v_q[i].t);
        sum_sp[i] = getSum(tree_first, 1, 1, i_ett, 1, in[v_q[i].s])
            + getSum(tree_first, 1, 1, i_ett, 1, in[v_q[i].t])
            - 2 * getSum(tree_first, 1, 1, i_ett, 1, in[lca]);
    }

    while (true) {
        for (i = 0; i < MAX; i++) {
            graph[i].clear();
        }
        reset();

        bool flag = false;
        for (i = 0; i < q; i++) {
            if (l[i] + 1 == r[i]) continue;
            flag = true; graph[l[i] + r[i] >> 1].push_back(i);
        }
        if (!flag) break;

        for (i = 0; i < m; i++) {
            ll start = v_spt[i].s, end = v_spt[i].e, v = v_spt[i].val;
            if (in[end] <= in[start] && in[start] <= out[end]) { swap(start, end); }
            update(tree_cpt, 1, 1, i_ett, in[end], v);
            update(tree_cpt, 1, 1, i_ett, out[end], -v);
            update(tree_cnt, 1, 1, i_ett, in[end], 1);
            update(tree_cnt, 1, 1, i_ett, out[end], -1);

            for (int next : graph[i]) {
                int lca = getLCA(v_q[next].s, v_q[next].t);
                ll currSp = getSum(tree_cpt, 1, 1, i_ett, 1, in[v_q[next].s])
                    + getSum(tree_cpt, 1, 1, i_ett, 1, in[v_q[next].t])
                    - 2 * getSum(tree_cpt, 1, 1, i_ett, 1, in[lca]);
                ll currCnt = getSum(tree_cnt, 1, 1, i_ett, 1, in[v_q[next].s])
                    + getSum(tree_cnt, 1, 1, i_ett, 1, in[v_q[next].t])
                    - 2 * getSum(tree_cnt, 1, 1, i_ett, 1, in[lca]);

                if (currSp <= v_q[next].y) {
                    ret[next] = max((ll)ret[next], v_q[next].x - sum_sp[next] + currCnt);
                    l[next] = i;
                }
                else { r[next] = i; }
            }
        }
    }

    for (i = 0; i < q; i++) {
        if (ret[i] == -1 && v_q[i].x >= sum_sp[i]) {
            ret[i] = v_q[i].x - sum_sp[i];
        }
        cout << ret[i] << '\n';
    }
}

int main() {
    fastIO();
    input();
    solve();
    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void update(ll*, int, int, int, int, ll)':
currencies.cpp:84:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int lidx = curr << 1, ridx = lidx | 1, mid = start + end >> 1;
      |                                                  ~~~~~~^~~~~
currencies.cpp: In function 'll getSum(ll*, int, int, int, int, int)':
currencies.cpp:93:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |     int lidx = curr << 1, ridx = lidx | 1, mid = start + end >> 1;
      |                                                  ~~~~~~^~~~~
currencies.cpp: In function 'void reset(int, int, int)':
currencies.cpp:100:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |     int mid = start + end >> 1;
      |               ~~~~~~^~~~~
currencies.cpp: In function 'void solve()':
currencies.cpp:161:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  161 |             flag = true; graph[l[i] + r[i] >> 1].push_back(i);
      |                                ~~~~~^~~~~~

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