Submission #1124524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124524		emptypringlescan	Two Currencies (JOI23_currencies)	C++17	100 / 100	1267 ms	463548 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
struct node{
	long long val,cnt;
	node *l, *r;
	node(long long V, long long C){
		val=V;
		cnt=C;
		l=r=NULL;
	}
	node(node* le, node* ri){
		l=le;
		r=ri;
		val=l->val+r->val;
		cnt=l->cnt+r->cnt;
	}
};

void prop(node* nd){
	if(nd->l==NULL){
		nd->r=new node(0LL,0LL);
		nd->l=new node(0LL,0LL);
	}
}
node* update(node* lol, int s, int e, int x){
	if(s==e) return new node(lol->val+s,lol->cnt+1);
	int mid=(s+e)/2;
	prop(lol);
	if(x<=mid) return new node(update(lol->l,s,mid,x),lol->r);
	else return new node(lol->l,update(lol->r,mid+1,e,x));
}
long long bsta(node* base, node* base2, node* one, node* two, int s, int e, long long V){
	long long tcnt=one->cnt+two->cnt-base->cnt-base2->cnt;
	if(s==e){
		return min(tcnt,V/(long long)s);
	}
	int mid=(s+e)/2;
	prop(base); prop(base2); prop(one); prop(two);
	long long ltcnt=one->l->cnt+two->l->cnt-base->l->cnt-base2->l->cnt;
	long long ltval=one->l->val+two->l->val-base->l->val-base2->l->val;
	if(ltval>V) return bsta(base->l,base2->l,one->l,two->l,s,mid,V);
	else return ltcnt+bsta(base->r,base2->r,one->r,two->r,mid+1,e,V-ltval);
}
node* nodes[200005];
vector<int> adj[200005];
long long cost[200005];
int par[200005];
void dfs(int x, int p){
	nodes[x]=update(nodes[p],0,1000000005,cost[x]);
	for(int i:adj[x]){
		if(i==p) continue;
		par[i]=x;
		dfs(i,x);
	}
}
const int MAXN = 200050;
const int LOGN = 20;
int p[LOGN+1][MAXN], h[MAXN];   //h: number of edges from root
bitset<MAXN> visited;
void dfss(int x) {
    if (visited[x]) return;
    visited[x] = 1LL;
    for (int k = 0LL; k < LOGN; ++k) {
        if (p[k][x] == -1LL) break;
        p[k+1LL][x] = p[k][p[k][x]];
    }
    for (int it:adj[x]) {
        if (visited[it]) continue;
        p[0][it] = x;
        h[it] = h[x] + 1LL;
        dfss(it);
    }
}

/* Query */
int lca(int a, int b) { //h[a] < h[b]
    if (h[a] > h[b]) swap(a, b);
    /* advance b by h[b] - h[a] parents */
    for (int k = 0, d = h[b] - h[a]; k < LOGN; ++k) {
        if (d & (1<<k))  b = p[k][b];
    }
    if (a == b) return a;
    assert(h[a] == h[b]); //same height
    /* to be continued */
    for (int k = LOGN-1; k >= 0; --k) {
        if (p[k][a] != p[k][b]) 
            a = p[k][a], b = p[k][b];
    }
    assert(p[0][a] == p[0][b]);        //same immediate parent
    return p[0][a];
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(p,-1,sizeof(p));
	int n,m,q;
	cin >> n >> m >> q;
	vector<pair<int,int> > edges;
	for(int i=0; i<n-1; i++){
		int a,b;
		cin >> a >> b;
		edges.push_back({a,b});
	}
	int cnt=n+1LL;
	for(int i=0; i<m; i++){
		int a;
		long long b;
		cin >> a >> b;
		cost[cnt]=b;
		edges.push_back({cnt,edges[a-1LL].second});
		edges[a-1LL].second=cnt;
		cnt++;
	}
	for(auto i:edges){
		adj[i.first].push_back(i.second);
		adj[i.second].push_back(i.first);
	}
	nodes[0]=new node(0LL,0LL);
	dfs(1LL,0LL);
	dfss(1LL);
	for(int i=0; i<q; i++){
		int a,b;
		long long c,d;
		cin >> a >> b >> c >> d;
		int o=lca(a,b);
		long long yes=bsta(nodes[o],nodes[o],nodes[a],nodes[b],0,1000000005,d);
		long long ret=c-(h[a]+h[b]-2*h[o]-yes);
		if(ret<0) cout << -1 << '\n';
		else cout << ret << '\n';
	}
}

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