Submission #924319

#	Time	Username	Problem	Language	Result	Execution time	Memory
924319		AlphaMale06	Two Currencies (JOI23_currencies)	C++17	100 / 100	1998 ms	167552 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define int long long

const int N = 1e5+5;

struct node{
    int val, cnt, lc, rc;
};


node pers[50*N];
int tin[N], tout[N], h[N];
vector<pair<int, int>> cst;
vector<int> adj[N];
int timer=0;
int n, m, q;
vector<pair<int, int>> edges;
int p[N][18];
vector<int> roots;
int nodenum=0;
void dfs(int v, int par){
    p[v][0]=par;
    for(int i=1; i<18; i++){
        p[v][i]=p[p[v][i-1]][i-1];
    }
    tin[v]=timer++;
    h[v]=h[par]+1;
    for(int to : adj[v]){
        if(to!=par)dfs(to, v);
    }
    tout[v]=timer++;
}

void Build(int v, int l, int r){
    if(l>r)return;
    nodenum++;
    if(l==r){
        pers[v]={0, 0, -1, -1};
        return;
    }
    int mid=l+r>>1;
    if(l<=mid){
        Build(2*v, l, mid);
        pers[v].lc=2*v;
    }
    if(r>=mid+1){
        Build(2*v+1, mid+1, r);
        pers[v].rc=2*v+1;
    }
}

void Update(int v, int l, int r, int ind, int val, int ps){
    if(l==r){
        pers[nodenum]={pers[v].val+val, pers[v].cnt+ps, -1, -1};
        nodenum++;
        return;
    }
    int mid=l+r>>1;
    if(l<=ind && ind<=mid){
        Update(pers[v].lc, l, mid, ind, val, ps);
        int child=pers[v].rc;
        pers[nodenum]={pers[child].val+pers[nodenum-1].val, pers[child].cnt+pers[nodenum-1].cnt, nodenum-1, child};
        nodenum++;
    }
    if(mid+1<=ind && ind<=r){
        Update(pers[v].rc, mid+1, r, ind, val, ps);
        int child=pers[v].lc;
        pers[nodenum]={pers[child].val+pers[nodenum-1].val, pers[child].cnt+pers[nodenum-1].cnt, child, nodenum-1};
        nodenum++;
    }
}

pair<int, int> Get(int v, int l, int r, int L, int R){
    if(l>R || r<L)return {0, 0};
    if(l>=L && r<=R)return {pers[v].val, pers[v].cnt};
    int mid=l+r>>1;
    pair<int, int> lft=Get(pers[v].lc, l, mid, L, R);
    pair<int, int> rgt=Get(pers[v].rc, mid+1, r, L, R);
    return {lft.F+rgt.F, lft.S+rgt.S};
}

bool anc(int u, int v){
    if(tin[u]<=tin[v] && tout[u]>=tout[v])return 1;
    return 0;
}

int lca(int u, int v){
    if(anc(u, v))return u;
    if(anc(v, u))return v;
    for(int i=17; i>=0; i--){
        if(!anc(p[u][i], v)){
            u=p[u][i];
        }
    }
    return p[u][0];
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i=0; i<n-1; i++){
        int a, b;
        cin >> a >> b;
        edges.pb({a, b});
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(1, 1);
    for(auto & p : edges){
        if(h[p.F]>h[p.S])swap(p.F, p.S);
    }
    for(int i=0; i<m; i++){
        int ind, val;
        cin >> ind >> val;
        cst.pb({val, edges[ind-1].S});
    }
    sort(cst.begin(), cst.end());
    roots.pb(0);
    Build(0, 0, timer-1);
    for(int i=0; i< m; i++){
        Update(roots.back(), 0, timer-1, tin[cst[i].S], cst[i].F, 1);
        roots.pb(nodenum-1);
        Update(roots.back(), 0, timer-1, tout[cst[i].S], -cst[i].F, -1);
        roots.pb(nodenum-1);
    }
    while(q--){
        int a, b, x, y;
        cin >> a >> b >> x >> y;
        int lc=lca(a, b);
        int dist=Get(roots.back(), 0, timer-1, 0, tin[a]).S+Get(roots.back(), 0, timer-1, 0, tin[b]).S-2*Get(roots.back(), 0, timer-1, 0, tin[lc]).S;
        int l=0; int r=roots.size()/2;
        int ans=1e9;
        while(l<=r){
            int s = l+r>>1;
            int root=roots[2*s];
            pair<int, int> lft=Get(root, 0, timer-1, 0, tin[a]);
            pair<int, int> rgt=Get(root, 0, timer-1, 0, tin[b]);
            pair<int, int> lcg=Get(root, 0, timer-1, 0, tin[lc]);
            if(lft.F+rgt.F-2*lcg.F<=y){
                l=s+1;
                ans=dist-lft.S-rgt.S+2*lcg.S;
            }
            else r=s-1;
        }
        cout << max(-1ll, x-ans) << '\n';
    }
}

Compilation message (stderr)

currencies.cpp: In function 'void Build(long long int, long long int, long long int)':
currencies.cpp:47:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int mid=l+r>>1;
      |             ~^~
currencies.cpp: In function 'void Update(long long int, long long int, long long int, long long int, long long int, long long int)':
currencies.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     int mid=l+r>>1;
      |             ~^~
currencies.cpp: In function 'std::pair<long long int, long long int> Get(long long int, long long int, long long int, long long int, long long int)':
currencies.cpp:82:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     int mid=l+r>>1;
      |             ~^~
currencies.cpp: In function 'int main()':
currencies.cpp:142:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  142 |             int s = l+r>>1;
      |                     ~^~

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