oj.uz

Submission #844173

# Submission time Handle Problem Language Result Execution time Memory
844173 2023-09-05T10:40:02 Z Quadrilateral Two Currencies (JOI23_currencies) C++17
100 / 100
 3988 ms 60496 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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 (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[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 (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, 1, 1, i_ett, in[end], 1);
        update(tree_first, 1, 1, i_ett, 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, 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 (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, 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 (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

currencies.cpp: In function 'void getParent()':
currencies.cpp:54:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   54 |     for (register int h = 1; h <= max_h; h++) {
      |                       ^
currencies.cpp:55:27: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   55 |         for (register int x = 2; x <= n; x++) {
      |                           ^
currencies.cpp: In function 'int getLCA(int, int)':
currencies.cpp:65:27: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   65 |         for (register int j = 0; diff > 0; j++) {
      |                           ^
currencies.cpp:72:27: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   72 |         for (register int k = max_h; k >= 0; k--) {
      |                           ^
currencies.cpp: In function 'void update(ll*, int, int, int, int, ll)':
currencies.cpp:86:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |     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:95:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |     int lidx = curr << 1, ridx = lidx | 1, mid = start + end >> 1;
      |                                                  ~~~~~~^~~~~
currencies.cpp: In function 'void reset(int, int, int)':
currencies.cpp:102:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |     int mid = start + end >> 1;
      |               ~~~~~~^~~~~
currencies.cpp: In function 'void solve()':
currencies.cpp:138:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  138 |     for (register int i = 0; i < q; i++) { l[i] = -1, r[i] = m; }
      |                       ^
currencies.cpp:140:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  140 |     for (register int i = 0; i < m; i++) {
      |                       ^
currencies.cpp:147:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  147 |     for (register int i = 0; i < q; i++) {
      |                       ^
currencies.cpp:161:27: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  161 |         for (register int i = 0; i < q; i++) {
      |                           ^
currencies.cpp:163:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  163 |             flag = true; graph[l[i] + r[i] >> 1].push_back(i);
      |                                ~~~~~^~~~~~
currencies.cpp:167:27: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  167 |         for (register int i = 0; i < m; i++) {
      |                           ^
currencies.cpp:193:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  193 |     for (register int i = 0; i < q; i++) {
      |                       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 3 ms 12632 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 17 ms 14936 KB Output is correct
6 Correct 20 ms 13144 KB Output is correct
7 Correct 19 ms 13144 KB Output is correct
8 Correct 23 ms 13180 KB Output is correct
9 Correct 22 ms 13200 KB Output is correct
10 Correct 23 ms 13220 KB Output is correct
11 Correct 22 ms 13148 KB Output is correct
12 Correct 22 ms 13144 KB Output is correct
13 Correct 30 ms 15192 KB Output is correct
14 Correct 24 ms 15396 KB Output is correct
15 Correct 30 ms 15300 KB Output is correct
16 Correct 24 ms 15192 KB Output is correct
17 Correct 24 ms 15260 KB Output is correct
18 Correct 23 ms 15196 KB Output is correct
19 Correct 22 ms 13144 KB Output is correct
20 Correct 21 ms 13216 KB Output is correct
21 Correct 22 ms 13400 KB Output is correct
22 Correct 20 ms 13148 KB Output is correct
23 Correct 17 ms 13180 KB Output is correct
24 Correct 18 ms 13144 KB Output is correct
25 Correct 18 ms 13148 KB Output is correct
26 Correct 20 ms 13144 KB Output is correct
27 Correct 16 ms 15196 KB Output is correct
28 Correct 17 ms 13400 KB Output is correct
29 Correct 18 ms 13200 KB Output is correct
30 Correct 22 ms 13144 KB Output is correct
31 Correct 24 ms 13652 KB Output is correct
32 Correct 22 ms 13144 KB Output is correct
33 Correct 23 ms 17364 KB Output is correct
34 Correct 23 ms 15192 KB Output is correct
35 Correct 25 ms 15448 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 22 ms 13144 KB Output is correct
3 Correct 23 ms 13148 KB Output is correct
4 Correct 22 ms 13208 KB Output is correct
5 Correct 1988 ms 44648 KB Output is correct
6 Correct 2234 ms 47100 KB Output is correct
7 Correct 2184 ms 47376 KB Output is correct
8 Correct 1775 ms 43036 KB Output is correct
9 Correct 1757 ms 43924 KB Output is correct
10 Correct 2879 ms 49288 KB Output is correct
11 Correct 2896 ms 49260 KB Output is correct
12 Correct 3120 ms 49156 KB Output is correct
13 Correct 3006 ms 49312 KB Output is correct
14 Correct 3176 ms 49228 KB Output is correct
15 Correct 3988 ms 58356 KB Output is correct
16 Correct 3502 ms 59788 KB Output is correct
17 Correct 3342 ms 58220 KB Output is correct
18 Correct 3188 ms 51848 KB Output is correct
19 Correct 3126 ms 51904 KB Output is correct
20 Correct 3210 ms 52056 KB Output is correct
21 Correct 2442 ms 46988 KB Output is correct
22 Correct 2410 ms 47036 KB Output is correct
23 Correct 2459 ms 47600 KB Output is correct
24 Correct 2447 ms 47072 KB Output is correct
25 Correct 2005 ms 49372 KB Output is correct
26 Correct 2048 ms 48936 KB Output is correct
27 Correct 1917 ms 49500 KB Output is correct
28 Correct 1492 ms 50452 KB Output is correct
29 Correct 1457 ms 49112 KB Output is correct
30 Correct 1664 ms 48424 KB Output is correct
31 Correct 1675 ms 49284 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 23 ms 17624 KB Output is correct
3 Correct 23 ms 15192 KB Output is correct
4 Correct 23 ms 15192 KB Output is correct
5 Correct 1834 ms 53192 KB Output is correct
6 Correct 1828 ms 52844 KB Output is correct
7 Correct 2207 ms 44320 KB Output is correct
8 Correct 3178 ms 59356 KB Output is correct
9 Correct 3265 ms 59268 KB Output is correct
10 Correct 3199 ms 59444 KB Output is correct
11 Correct 2106 ms 59840 KB Output is correct
12 Correct 2118 ms 59668 KB Output is correct
13 Correct 2227 ms 59488 KB Output is correct
14 Correct 1645 ms 59628 KB Output is correct
15 Correct 1585 ms 60496 KB Output is correct
16 Correct 1772 ms 59656 KB Output is correct
17 Correct 1797 ms 59864 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 3 ms 12632 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 17 ms 14936 KB Output is correct
6 Correct 20 ms 13144 KB Output is correct
7 Correct 19 ms 13144 KB Output is correct
8 Correct 23 ms 13180 KB Output is correct
9 Correct 22 ms 13200 KB Output is correct
10 Correct 23 ms 13220 KB Output is correct
11 Correct 22 ms 13148 KB Output is correct
12 Correct 22 ms 13144 KB Output is correct
13 Correct 30 ms 15192 KB Output is correct
14 Correct 24 ms 15396 KB Output is correct
15 Correct 30 ms 15300 KB Output is correct
16 Correct 24 ms 15192 KB Output is correct
17 Correct 24 ms 15260 KB Output is correct
18 Correct 23 ms 15196 KB Output is correct
19 Correct 22 ms 13144 KB Output is correct
20 Correct 21 ms 13216 KB Output is correct
21 Correct 22 ms 13400 KB Output is correct
22 Correct 20 ms 13148 KB Output is correct
23 Correct 17 ms 13180 KB Output is correct
24 Correct 18 ms 13144 KB Output is correct
25 Correct 18 ms 13148 KB Output is correct
26 Correct 20 ms 13144 KB Output is correct
27 Correct 16 ms 15196 KB Output is correct
28 Correct 17 ms 13400 KB Output is correct
29 Correct 18 ms 13200 KB Output is correct
30 Correct 22 ms 13144 KB Output is correct
31 Correct 24 ms 13652 KB Output is correct
32 Correct 22 ms 13144 KB Output is correct
33 Correct 23 ms 17364 KB Output is correct
34 Correct 23 ms 15192 KB Output is correct
35 Correct 25 ms 15448 KB Output is correct
36 Correct 2 ms 12636 KB Output is correct
37 Correct 22 ms 13144 KB Output is correct
38 Correct 23 ms 13148 KB Output is correct
39 Correct 22 ms 13208 KB Output is correct
40 Correct 1988 ms 44648 KB Output is correct
41 Correct 2234 ms 47100 KB Output is correct
42 Correct 2184 ms 47376 KB Output is correct
43 Correct 1775 ms 43036 KB Output is correct
44 Correct 1757 ms 43924 KB Output is correct
45 Correct 2879 ms 49288 KB Output is correct
46 Correct 2896 ms 49260 KB Output is correct
47 Correct 3120 ms 49156 KB Output is correct
48 Correct 3006 ms 49312 KB Output is correct
49 Correct 3176 ms 49228 KB Output is correct
50 Correct 3988 ms 58356 KB Output is correct
51 Correct 3502 ms 59788 KB Output is correct
52 Correct 3342 ms 58220 KB Output is correct
53 Correct 3188 ms 51848 KB Output is correct
54 Correct 3126 ms 51904 KB Output is correct
55 Correct 3210 ms 52056 KB Output is correct
56 Correct 2442 ms 46988 KB Output is correct
57 Correct 2410 ms 47036 KB Output is correct
58 Correct 2459 ms 47600 KB Output is correct
59 Correct 2447 ms 47072 KB Output is correct
60 Correct 2005 ms 49372 KB Output is correct
61 Correct 2048 ms 48936 KB Output is correct
62 Correct 1917 ms 49500 KB Output is correct
63 Correct 1492 ms 50452 KB Output is correct
64 Correct 1457 ms 49112 KB Output is correct
65 Correct 1664 ms 48424 KB Output is correct
66 Correct 1675 ms 49284 KB Output is correct
67 Correct 2 ms 12632 KB Output is correct
68 Correct 23 ms 17624 KB Output is correct
69 Correct 23 ms 15192 KB Output is correct
70 Correct 23 ms 15192 KB Output is correct
71 Correct 1834 ms 53192 KB Output is correct
72 Correct 1828 ms 52844 KB Output is correct
73 Correct 2207 ms 44320 KB Output is correct
74 Correct 3178 ms 59356 KB Output is correct
75 Correct 3265 ms 59268 KB Output is correct
76 Correct 3199 ms 59444 KB Output is correct
77 Correct 2106 ms 59840 KB Output is correct
78 Correct 2118 ms 59668 KB Output is correct
79 Correct 2227 ms 59488 KB Output is correct
80 Correct 1645 ms 59628 KB Output is correct
81 Correct 1585 ms 60496 KB Output is correct
82 Correct 1772 ms 59656 KB Output is correct
83 Correct 1797 ms 59864 KB Output is correct
84 Correct 1931 ms 43552 KB Output is correct
85 Correct 1730 ms 37692 KB Output is correct
86 Correct 1465 ms 37516 KB Output is correct
87 Correct 2736 ms 49688 KB Output is correct
88 Correct 2752 ms 50276 KB Output is correct
89 Correct 2728 ms 49548 KB Output is correct
90 Correct 2768 ms 50280 KB Output is correct
91 Correct 2785 ms 50068 KB Output is correct
92 Correct 3398 ms 56532 KB Output is correct
93 Correct 3360 ms 57984 KB Output is correct
94 Correct 3111 ms 52124 KB Output is correct
95 Correct 3140 ms 51480 KB Output is correct
96 Correct 3176 ms 51792 KB Output is correct
97 Correct 3297 ms 51440 KB Output is correct
98 Correct 2601 ms 47192 KB Output is correct
99 Correct 2869 ms 47556 KB Output is correct
100 Correct 2842 ms 47064 KB Output is correct
101 Correct 2826 ms 47036 KB Output is correct
102 Correct 2182 ms 49664 KB Output is correct
103 Correct 2469 ms 49204 KB Output is correct
104 Correct 2464 ms 49820 KB Output is correct
105 Correct 1669 ms 48592 KB Output is correct
106 Correct 1585 ms 49640 KB Output is correct
107 Correct 1900 ms 48520 KB Output is correct
108 Correct 1877 ms 48400 KB Output is correct