oj.uz

Submission #844149

# Submission time Handle Problem Language Result Execution time Memory
844149 2023-09-05T10:11:49 Z Quadrilateral Two Currencies (JOI23_currencies) C++17
100 / 100
 3640 ms 60268 KB 
#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;
    ll vl = getSum(tree, lidx, start, mid, t_start, t_end);
    ll vr = getSum(tree, ridx, mid+1, end, t_start, t_end);
    return vl + vr;
}

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;
        spt tmp = {arr[a].MIN, arr[a].MAXNUM, 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

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:54: 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:102:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |     int mid = start + end >> 1;
      |               ~~~~~~^~~~~
currencies.cpp: In function 'void input()':
currencies.cpp:123:13: warning: unused variable 'tmp' [-Wunused-variable]
  123 |         spt tmp = {arr[a].MIN, arr[a].MAXNUM, b};
      |             ^~~
currencies.cpp: In function 'void solve()':
currencies.cpp:164:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  164 |             flag = true; graph[l[i] + r[i] >> 1].push_back(i);
      |                                ~~~~~^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 17 ms 13148 KB Output is correct
6 Correct 21 ms 13148 KB Output is correct
7 Correct 18 ms 13148 KB Output is correct
8 Correct 23 ms 13216 KB Output is correct
9 Correct 23 ms 13144 KB Output is correct
10 Correct 23 ms 13148 KB Output is correct
11 Correct 23 ms 13228 KB Output is correct
12 Correct 23 ms 13148 KB Output is correct
13 Correct 24 ms 15192 KB Output is correct
14 Correct 24 ms 15196 KB Output is correct
15 Correct 24 ms 15196 KB Output is correct
16 Correct 24 ms 15196 KB Output is correct
17 Correct 27 ms 15596 KB Output is correct
18 Correct 25 ms 15448 KB Output is correct
19 Correct 21 ms 13220 KB Output is correct
20 Correct 21 ms 13252 KB Output is correct
21 Correct 21 ms 13148 KB Output is correct
22 Correct 21 ms 13148 KB Output is correct
23 Correct 17 ms 13148 KB Output is correct
24 Correct 18 ms 13108 KB Output is correct
25 Correct 18 ms 13148 KB Output is correct
26 Correct 16 ms 13148 KB Output is correct
27 Correct 15 ms 13236 KB Output is correct
28 Correct 17 ms 13148 KB Output is correct
29 Correct 17 ms 13148 KB Output is correct
30 Correct 24 ms 13180 KB Output is correct
31 Correct 23 ms 13244 KB Output is correct
32 Correct 24 ms 13148 KB Output is correct
33 Correct 24 ms 15192 KB Output is correct
34 Correct 24 ms 15196 KB Output is correct
35 Correct 24 ms 15336 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 23 ms 13212 KB Output is correct
3 Correct 22 ms 13208 KB Output is correct
4 Correct 23 ms 13148 KB Output is correct
5 Correct 1972 ms 45112 KB Output is correct
6 Correct 2162 ms 48144 KB Output is correct
7 Correct 2186 ms 46944 KB Output is correct
8 Correct 1666 ms 43528 KB Output is correct
9 Correct 1682 ms 43388 KB Output is correct
10 Correct 2962 ms 51004 KB Output is correct
11 Correct 2983 ms 50424 KB Output is correct
12 Correct 2923 ms 50432 KB Output is correct
13 Correct 2871 ms 50296 KB Output is correct
14 Correct 2966 ms 50704 KB Output is correct
15 Correct 3640 ms 59232 KB Output is correct
16 Correct 3295 ms 58952 KB Output is correct
17 Correct 3528 ms 59352 KB Output is correct
18 Correct 3317 ms 53140 KB Output is correct
19 Correct 3300 ms 52944 KB Output is correct
20 Correct 3251 ms 52828 KB Output is correct
21 Correct 2492 ms 47876 KB Output is correct
22 Correct 2526 ms 47996 KB Output is correct
23 Correct 2562 ms 48028 KB Output is correct
24 Correct 2541 ms 48048 KB Output is correct
25 Correct 2118 ms 50732 KB Output is correct
26 Correct 2067 ms 50384 KB Output is correct
27 Correct 2004 ms 51092 KB Output is correct
28 Correct 1485 ms 50920 KB Output is correct
29 Correct 1529 ms 49836 KB Output is correct
30 Correct 1709 ms 49612 KB Output is correct
31 Correct 1716 ms 49716 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 24 ms 15196 KB Output is correct
3 Correct 26 ms 15336 KB Output is correct
4 Correct 25 ms 15196 KB Output is correct
5 Correct 1999 ms 52684 KB Output is correct
6 Correct 1850 ms 52104 KB Output is correct
7 Correct 2255 ms 45648 KB Output is correct
8 Correct 3395 ms 59764 KB Output is correct
9 Correct 3389 ms 59380 KB Output is correct
10 Correct 3358 ms 59792 KB Output is correct
11 Correct 2148 ms 59460 KB Output is correct
12 Correct 2124 ms 59688 KB Output is correct
13 Correct 2215 ms 59520 KB Output is correct
14 Correct 1615 ms 59628 KB Output is correct
15 Correct 1616 ms 60268 KB Output is correct
16 Correct 1928 ms 59500 KB Output is correct
17 Correct 1889 ms 59524 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 17 ms 13148 KB Output is correct
6 Correct 21 ms 13148 KB Output is correct
7 Correct 18 ms 13148 KB Output is correct
8 Correct 23 ms 13216 KB Output is correct
9 Correct 23 ms 13144 KB Output is correct
10 Correct 23 ms 13148 KB Output is correct
11 Correct 23 ms 13228 KB Output is correct
12 Correct 23 ms 13148 KB Output is correct
13 Correct 24 ms 15192 KB Output is correct
14 Correct 24 ms 15196 KB Output is correct
15 Correct 24 ms 15196 KB Output is correct
16 Correct 24 ms 15196 KB Output is correct
17 Correct 27 ms 15596 KB Output is correct
18 Correct 25 ms 15448 KB Output is correct
19 Correct 21 ms 13220 KB Output is correct
20 Correct 21 ms 13252 KB Output is correct
21 Correct 21 ms 13148 KB Output is correct
22 Correct 21 ms 13148 KB Output is correct
23 Correct 17 ms 13148 KB Output is correct
24 Correct 18 ms 13108 KB Output is correct
25 Correct 18 ms 13148 KB Output is correct
26 Correct 16 ms 13148 KB Output is correct
27 Correct 15 ms 13236 KB Output is correct
28 Correct 17 ms 13148 KB Output is correct
29 Correct 17 ms 13148 KB Output is correct
30 Correct 24 ms 13180 KB Output is correct
31 Correct 23 ms 13244 KB Output is correct
32 Correct 24 ms 13148 KB Output is correct
33 Correct 24 ms 15192 KB Output is correct
34 Correct 24 ms 15196 KB Output is correct
35 Correct 24 ms 15336 KB Output is correct
36 Correct 3 ms 12636 KB Output is correct
37 Correct 23 ms 13212 KB Output is correct
38 Correct 22 ms 13208 KB Output is correct
39 Correct 23 ms 13148 KB Output is correct
40 Correct 1972 ms 45112 KB Output is correct
41 Correct 2162 ms 48144 KB Output is correct
42 Correct 2186 ms 46944 KB Output is correct
43 Correct 1666 ms 43528 KB Output is correct
44 Correct 1682 ms 43388 KB Output is correct
45 Correct 2962 ms 51004 KB Output is correct
46 Correct 2983 ms 50424 KB Output is correct
47 Correct 2923 ms 50432 KB Output is correct
48 Correct 2871 ms 50296 KB Output is correct
49 Correct 2966 ms 50704 KB Output is correct
50 Correct 3640 ms 59232 KB Output is correct
51 Correct 3295 ms 58952 KB Output is correct
52 Correct 3528 ms 59352 KB Output is correct
53 Correct 3317 ms 53140 KB Output is correct
54 Correct 3300 ms 52944 KB Output is correct
55 Correct 3251 ms 52828 KB Output is correct
56 Correct 2492 ms 47876 KB Output is correct
57 Correct 2526 ms 47996 KB Output is correct
58 Correct 2562 ms 48028 KB Output is correct
59 Correct 2541 ms 48048 KB Output is correct
60 Correct 2118 ms 50732 KB Output is correct
61 Correct 2067 ms 50384 KB Output is correct
62 Correct 2004 ms 51092 KB Output is correct
63 Correct 1485 ms 50920 KB Output is correct
64 Correct 1529 ms 49836 KB Output is correct
65 Correct 1709 ms 49612 KB Output is correct
66 Correct 1716 ms 49716 KB Output is correct
67 Correct 2 ms 12636 KB Output is correct
68 Correct 24 ms 15196 KB Output is correct
69 Correct 26 ms 15336 KB Output is correct
70 Correct 25 ms 15196 KB Output is correct
71 Correct 1999 ms 52684 KB Output is correct
72 Correct 1850 ms 52104 KB Output is correct
73 Correct 2255 ms 45648 KB Output is correct
74 Correct 3395 ms 59764 KB Output is correct
75 Correct 3389 ms 59380 KB Output is correct
76 Correct 3358 ms 59792 KB Output is correct
77 Correct 2148 ms 59460 KB Output is correct
78 Correct 2124 ms 59688 KB Output is correct
79 Correct 2215 ms 59520 KB Output is correct
80 Correct 1615 ms 59628 KB Output is correct
81 Correct 1616 ms 60268 KB Output is correct
82 Correct 1928 ms 59500 KB Output is correct
83 Correct 1889 ms 59524 KB Output is correct
84 Correct 1950 ms 44540 KB Output is correct
85 Correct 1826 ms 38464 KB Output is correct
86 Correct 1669 ms 38108 KB Output is correct
87 Correct 2904 ms 50488 KB Output is correct
88 Correct 2784 ms 51176 KB Output is correct
89 Correct 2827 ms 50268 KB Output is correct
90 Correct 3079 ms 50680 KB Output is correct
91 Correct 2780 ms 51056 KB Output is correct
92 Correct 3558 ms 56856 KB Output is correct
93 Correct 3519 ms 58120 KB Output is correct
94 Correct 3351 ms 53160 KB Output is correct
95 Correct 3394 ms 52832 KB Output is correct
96 Correct 3212 ms 52916 KB Output is correct
97 Correct 3168 ms 52796 KB Output is correct
98 Correct 2553 ms 48108 KB Output is correct
99 Correct 2625 ms 47856 KB Output is correct
100 Correct 2587 ms 48296 KB Output is correct
101 Correct 2546 ms 48292 KB Output is correct
102 Correct 2009 ms 50680 KB Output is correct
103 Correct 2096 ms 50668 KB Output is correct
104 Correct 2094 ms 50348 KB Output is correct
105 Correct 1454 ms 49732 KB Output is correct
106 Correct 1473 ms 50704 KB Output is correct
107 Correct 1694 ms 49592 KB Output is correct
108 Correct 1733 ms 49528 KB Output is correct