Submission #844195

#	Time	Username	Problem	Language	Result	Execution time	Memory
844195		Quadrilateral	Two Currencies (JOI23_currencies)	C++14	0 / 100	5052 ms	12636 KiB

currencies

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define MAX 100010
#define MIN first
#define MAXNUM second
#define base 262144
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 (register int h = 1; h <= max_h; h++) {
        for (register 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 (register int j = 0; diff > 0; j++) {
            if (diff & 1) { a = par[j][a]; }
            diff >>= 1;
        }
    }

    if (a != b) {
        for (register 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[base], tree_first[base], tree_cnt[base];

void update(ll tree[], int x, ll v) {
    x |= base; tree[x] = v;
    while (x >> 1) {
        tree[x] = tree[x << 1] + tree[x << 1 | 1];
    }
}

ll getSum(ll tree[], int l, int r) {
    l |= base; r |= base;
    int ret = 0;
    while (l <= r) {
        if (l & 1) ret += tree[l++];
        if (~r & 1) ret += tree[r--];
        l >>= 1, r >>= 1;
    }
    return ret;
}

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 (register int i = 0; i < q; i++) { l[i] = -1, r[i] = m; }

    for (register int 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, in[end], 1);
        update(tree_first, out[end], -1);
    }

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

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

        bool flag = false;
        for (register int 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 (register int 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, in[end], v);
            update(tree_cpt, out[end], -v);
            update(tree_cnt, in[end], 1);
            update(tree_cnt, 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, in[v_q[next].s])
                    + getSum(tree_cpt, 1, in[v_q[next].t])
                    - 2 * getSum(tree_cpt, 1, in[lca]);
                ll currCnt = getSum(tree_cnt, 1, in[v_q[next].s])
                    + getSum(tree_cnt, 1, in[v_q[next].t])
                    - 2 * getSum(tree_cnt, 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 (register int 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 reset(int, int, int)':
currencies.cpp:104:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |     int mid = start + end >> 1;
      |               ~~~~~~^~~~~
currencies.cpp: In function 'void solve()':
currencies.cpp:165:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  165 |             flag = true; graph[l[i] + r[i] >> 1].push_back(i);
      |                                ~~~~~^~~~~~

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