Submission #844149

#	Time	Username	Problem	Language	Result	Execution time	Memory
844149		Quadrilateral	Two Currencies (JOI23_currencies)	C++17	100 / 100	3640 ms	60268 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;
    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 (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: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 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32