Submission #774328

#	Time	Username	Problem	Language	Result	Execution time	Memory
774328		HossamHero7	Two Currencies (JOI23_currencies)	C++14	100 / 100	840 ms	193228 KiB

currencies

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define endl '\n'
int pt = 0;
pair<ll,ll> tree[3*6000000];
int lft[3*6000000];
int rt[3*6000000];
int P[100005][30];
int root[100005];
vector<int> dep(100005);
vector<ll> w[100005];
vector<pair<int,int>> adj[100005];
int P2[100005][30];
void update(int node,int prv,int l,int r,ll idx,ll val){
    if(l == r) return tree[node] = make_pair(tree[prv].first+l*val,tree[prv].second+val),void();
    int md = l + r >> 1;
    if(idx<=md){
        int tmp = lft[prv];
        lft[node] = ++pt;
        rt[node] = rt[prv];
        update(lft[node],tmp,l,md,idx,val);
    }
    else {
        int tmp = rt[prv];
        rt[node] = ++pt;
        lft[node] = lft[prv];
        update(rt[node],tmp,md+1,r,idx,val);
    }
    tree[node] = make_pair(tree[lft[node]].first+tree[rt[node]].first,tree[lft[node]].second+tree[rt[node]].second);
}
void update(int a,int b,ll val,ll frq){
    if(!root[a]) root[a] = ++pt;
    update(root[a],root[b],1,1e9,val,frq);
}
void dfs(int node,int par,int id){
    P[node][0] = par;
    P2[node][0] = w[id].size();
    for(int k=1;k<30;k++) P[node][k] = P[P[node][k-1]][k-1],P2[node][k] = P2[node][k-1] + P2[P[node][k-1]][k-1];
    for(auto e : adj[node]){
        int ch = e.first;
        if(ch == par) continue;
        dep[ch] = dep[node] + 1;
        update(ch,node,1,0);
        for(auto ww : w[e.second]){
            update(ch,ch,ww,1);
        }
        dfs(ch,node,e.second);
    }
}
int lca(int a,int b){
	if(dep[a]<dep[b]) swap(a,b);
	if(a == b) return a;
	for(int k=29;k>=0;k--){
		if(dep[a]-(1<<k)>=dep[b]){
			a = P[a][k];
		}
	}
	if(a == b){
		return a;
	}
	for(int i=29;i>=0;i--){
		if(P[a][i]!=P[b][i]){
			a = P[a][i];
			b = P[b][i];
		}
	}
	return P[a][0];
}
int calc(int a,int b){
	if(dep[a]<dep[b]) swap(a,b);
	if(a == b) return a;
	int ret = 0;
	for(int k=29;k>=0;k--){
		if(dep[a]-(1<<k)>=dep[b]){
			ret += P2[a][k];
			a = P[a][k];
		}
	}
	if(a == b){
		return ret;
	}
	for(int i=29;i>=0;i--){
		if(P[a][i]!=P[b][i]){
            ret += P2[a][i];
            ret += P2[b][i];
			a = P[a][i];
			b = P[b][i];
		}
	}
	ret += P2[a][0] + P2[b][0];
	return ret;
}
ll query(int a,int b,int c,int l,int r,ll x){
    if(l == r){
        ll z = tree[a].second+tree[b].second-2*tree[c].second;
        return min(x/(ll)l,z);
    }
    pair<ll,ll> sumOfL = make_pair(tree[lft[a]].first+tree[lft[b]].first-2LL*tree[lft[c]].first,tree[lft[a]].second+tree[lft[b]].second-2LL*tree[lft[c]].second);
    pair<ll,ll> sumOfR = make_pair(tree[rt[a]].first+tree[rt[b]].first-2LL*tree[rt[c]].first,tree[rt[a]].second+tree[rt[b]].second-2LL*tree[rt[c]].second);
    int md = l + r >> 1;
    if(sumOfL.first>x) return query(lft[a],lft[b],lft[c],l,md,x);
    return sumOfL.second + query(rt[a],rt[b],rt[c],md+1,r,x-sumOfL.first);
}
void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back({b,i+1});
        adj[b].push_back({a,i+1});
    }
    for(int i=0;i<m;i++){
        ll a,b;
        cin>>a>>b;
        w[a].push_back(b);
    }
    dfs(1,0,0);/*
    for(int i=1;i<=n;i++) {
        cout<<tree[root[i]].first<<' ';
    }
    cout<<endl;*/
    while(q--){
        ll u,v,a,b;
        cin>>u>>v>>a>>b;
        ll z = query(root[u],root[v],root[lca(u,v)],1,1e9,b);
        ll ans = a - (calc(u,v)-z);
        cout<<(ans<0?-1:ans)<<endl;
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void update(int, int, int, int, ll, ll)':
currencies.cpp:18:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |     int md = l + r >> 1;
      |              ~~^~~
currencies.cpp: In function 'll query(int, int, int, int, int, ll)':
currencies.cpp:102:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |     int md = l + r >> 1;
      |              ~~^~~
currencies.cpp:101:17: warning: variable 'sumOfR' set but not used [-Wunused-but-set-variable]
  101 |     pair<ll,ll> sumOfR = make_pair(tree[rt[a]].first+tree[rt[b]].first-2LL*tree[rt[c]].first,tree[rt[a]].second+tree[rt[b]].second-2LL*tree[rt[c]].second);
      |                 ^~~~~~

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