Submission #970929

#	Time	Username	Problem	Language	Result	Execution time	Memory
970929		happy_node	Two Currencies (JOI23_currencies)	C++17	100 / 100	4543 ms	57416 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=1e5+5, MK=18;

int N,M,Q;

vector<int> qry[MX];

ll S[MX], T[MX], X[MX], Y[MX], ans[MX], lca[MX];

int L[MX], R[MX], U[MX], V[MX];

int up[MX][MK], tin[MX], tout[MX], timer=0;

struct segtree {
        ll t[4*MX], lazy[4*MX];

        void push(int v, int l, int r) {
        	t[v]+=lazy[v];
        	if(l!=r) {
        		lazy[2*v+0]+=lazy[v];
        		lazy[2*v+1]+=lazy[v];
        	}
        	lazy[v]=0;
        }
 
        void update(int v, int l, int r, int ql, int qr, int val) {
        	push(v,l,r);
                if(qr<l || r<ql) return;
                if(ql<=l && qr>=r) {
                        lazy[v]+=val;
                        push(v,l,r);
                        return;
                }
                int mid = (l + r) >> 1;
                update(v*2+0, l, mid+0, ql, qr, val);
                update(v*2+1, mid+1, r, ql, qr, val);
                t[v] = t[v*2+0] + t[v*2+1];
        }
 
        ll query(int v, int l, int r, int ql, int qr) {
        	push(v,l,r);
                if(ql > r || qr < l) return 0;
                if(ql <= l && qr >= r) return t[v];
                int mid = (l + r) >> 1;
                return query(v*2+0, l, mid+0, ql, qr) + query(v*2+1, mid+1, r, ql, qr);
        }

        void upd(int pos, ll val) {
        	update(1,1,N,tin[pos],tout[pos],val);
        }

        ll que(int a, int b) {
        	return query(1,1,N,tin[a],tin[a])-query(1,1,N,tin[b],tin[b]);
        }

        void reset() {
        	for(int i=0;i<4*MX;i++) t[i]=0,lazy[i]=0;
        }
} st, tt;

vector<int> adj[MX];
 
void dfs(int v, int p) {
        tin[v]=++timer;
        up[v][0]=p;
        for(int k = 1; k < MK; k++) {
                up[v][k]=up[up[v][k-1]][k-1];
        }
        for(auto u : adj[v]) {
                if(u == p) continue;
                dfs(u,v);
        }
        tout[v]=timer;
}
 
bool isAnc(int v, int anc) { 
        if(tin[anc]<=tin[v] && tout[v]<=tout[anc]) return 1;
        return 0;
}

int LCA(int u, int v) {
        if(isAnc(u, v)) return v;
        if(isAnc(v, u)) return u;
        for(int k=MK-1; k>=0;k--) {
                if(!isAnc(u, up[v][k]) && up[v][k]!=0) v = up[v][k];
        }
        return up[v][0];
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N>>M>>Q;

	for(int i=1;i<=N-1;i++) {
		int u,v;
		cin>>u>>v;

		adj[u].push_back(v);
		adj[v].push_back(u);
		U[i]=u;
		V[i]=v;
	}

	vector<pair<int,int>> e;
	e.push_back({0,0});

	for(int i=0;i<M;i++) {
		int p,c;
		cin>>p>>c;
		e.push_back({c,p});
	}

	dfs(1,0);

	sort(e.begin(),e.end());

	for(int i=0;i<Q;i++) {
		cin>>S[i]>>T[i]>>X[i]>>Y[i];
		L[i]=0,R[i]=M;
		int m=(L[i]+R[i])/2;
		lca[i]=LCA(S[i],T[i]);
		qry[m].push_back(i);
	}

	for(int i=1;i<=N-1;i++) {
		if(isAnc(V[i],U[i])) swap(U[i],V[i]); // V parentnya 
	}

	for(int ii=0;ii<20;ii++) {
		st.reset();
		tt.reset();
		// activate

		for(int i=1;i<=M;i++) {
			auto [c,p]=e[i];
			st.upd(U[p],1);
		}

		vector<pair<int,int>> nxt;

		for(int i=0;i<=M;i++) {
			auto [c,p]=e[i];
			if(i>0) {
				st.upd(U[p],-1);
				tt.upd(U[p],c);
			}

			for(auto id:qry[i]) {
				ll s=tt.que(S[id],lca[id])+tt.que(T[id],lca[id]);

				if(s<=Y[id]) {
					ans[id]=st.que(S[id],lca[id])+st.que(T[id],lca[id]);
					L[id]=i+1;
					if(L[id]<=R[id])
						nxt.push_back({(L[id]+R[id])/2, id});
				} else {
					R[id]=i-1;
					if(L[id]<=R[id])
						nxt.push_back({(L[id]+R[id])/2, id});
				}
			}
		}

		for(int i=0;i<=M;i++) qry[i].clear();
		for(auto [i,id]:nxt) qry[i].push_back(id);
	}
	
	for(int i=0;i<Q;i++) {
		if(ans[i]>X[i]) {
			cout<<-1<<'\n';
		} else {
			cout<<X[i]-ans[i]<<'\n';
		}
	}

}

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