Submission #1125074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125074		Tyx2019	Two Currencies (JOI23_currencies)	C++20	100 / 100	2567 ms	361896 KiB

currencies

#include <bits/stdc++.h>
#define int long long 
#define debug(x) if(0) cout << #x << " is " << x << endl;
using namespace std;
	int N, M, Q;

struct node{
	int32_t S, E, M;
	int V;
	node *l, *r;
	//range add, point query 
	node(int _S, int _E){
		S = _S;
		E = _E;
		V = 0;
		l = r = NULL;
		M = (S + E) >> 1;
	}
	node* cpy(){
		node *ret = new node(S, E);
		ret->S = S;
		ret->E = E;
		ret->l = l;
		ret->r = r;
		ret->M = M;
		ret->V = V;
		return ret;
	}
	int query(int start, int end){
		if(start == S && end == E){
			return V;
		}
		if(end <= M){
			if(l == NULL) return 0;
			return l->query(start, end);
		}
		if(start > M){
			if(r == NULL) return 0;
			return r->query(start, end);
		}
		int lAns, rAns;
		if(l == NULL) lAns = 0;
		else lAns = l->query(start, M);
		if(r == NULL) rAns = 0;
		else rAns = r->query(M + 1, end);
		return lAns + rAns;
	}
	void upd(int idx, int val){
		if(S == E){
			V += val;
			return;
		}
		if(idx <= M){
			if(l) l = l->cpy();
			else l = new node(S, M);
			l->upd(idx, val);
		}
		else{
			if(r) r = r->cpy();
			else r = new node(M + 1, E);
			r->upd(idx, val);
		}
		V += val;
	}
}*seggssum, *seggscnt;
const int maxN = 1e5 + 5;
vector<int> adj[maxN];
int order[maxN];
int cur = 0;
int mem[maxN][20];
int depth[maxN];
int streesz[maxN];
void dfs(int x, int par){
	order[x] = cur++;
	mem[x][0] = par;
	streesz[x] = 1;
	for(auto j:adj[x]){
		if(j == par) continue;
		depth[j] = depth[x] + 1;
		dfs(j, x);
		streesz[x] += streesz[j];
	}
}
int anc(int x, int k){
	int cur = x;
	for(int i=19;i>=0;i--){
		if(((1 << i) & k) != 0){
			cur = mem[cur][i];
		}
	}
	return cur;
}
int lcaa(int x, int y){
	if(depth[x] < depth[y]) swap(x, y);
	int k = depth[x] - depth[y];
	x = anc(x, k);
	assert(min(x, y) >= 1);
	assert(k >= 0);
	if(x == y) return x;
	for(int i=19;i>=0;i--){
		if(mem[x][i] != mem[y][i]){
			x = mem[x][i];
			y = mem[y][i];
		}
	}
	
	return mem[x][0];
}
main(){
	cin >> N >> M >> Q;
	seggssum = new node(0, N + 5);
	seggscnt = new node(0, N + 5);
	int A[N], B[N];
	for(int i=1;i<=N-1;i++) cin >> A[i] >> B[i];
	for(int i=1;i<=N-1;i++){
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	depth[1] = 0;
	dfs(1, -1);
	//2k
	for(int j=1;j<20;j++){
		for(int i=1;i<=N;i++){
			int hpar = mem[i][j-1];
			if(hpar == -1) mem[i][j] = -1;
			else mem[i][j] = mem[hpar][j-1];
		}
	}
	int C[M], P[M];
	for(int i=0;i<M;i++){
		cin >> P[i] >> C[i];
	}
	int S[Q], T[Q], X[Q], Y[Q], lca[Q];
	for(int i=0;i<Q;i++){
		cin >> S[i] >> T[i] >> X[i] >> Y[i];
		lca[i] = lcaa(S[i], T[i]);
	}
	vector<pair<int, int>> V;
	for(int i=0;i<M;i++){
		V.push_back({C[i], P[i]});
	}
	sort(V.begin(), V.end());
	node* sum[M + 5];
	node* count[M + 5];
	sum[0] = seggssum;
	count[0] = seggscnt;
	for(int i=1;i<=M;i++){
		int x = V[i-1].second;
		int bruh = A[x];
		if(depth[B[x]] >= depth[bruh]) bruh = B[x];
		sum[i] = sum[i-1]->cpy();
		sum[i]->upd(order[bruh], V[i-1].first);
		sum[i]->upd(order[bruh] + streesz[bruh], -V[i-1].first);
		count[i] = count[i-1]->cpy();
		count[i]->upd(order[bruh], 1);
		count[i]->upd(order[bruh] + streesz[bruh], -1);
	}
	debug("hi");
	for(int i=0;i<Q;i++){
		int lb = 0;
		int ub = M;
		while(ub > lb){
			int m = (ub + lb + 1) >> 1;
			int s = sum[m]->query(0, order[S[i]]);
			int t = sum[m]->query(0, order[T[i]]);
			int l = sum[m]->query(0, order[lca[i]]);
			if((s + t - (2 * l)) <= Y[i]) lb = m;
			else ub = m - 1;
		}

		int s = count[lb]->query(0, order[S[i]]);
		int t = count[lb]->query(0, order[T[i]]);
		int l = count[lb]->query(0, order[lca[i]]);
		int k = s + t - (2 * l);
		s = count[M]->query(0, order[S[i]]);
		t = count[M]->query(0, order[T[i]]);
		l = count[M]->query(0, order[lca[i]]);
		int tot = s + t - (2 * l);
		int nec = tot - k;
		int res = X[i] - nec;
		if(res < 0){
			cout << "-1\n";
		}
		else cout << res << '\n';
	}
	for(int i=1;i<=N;i++) debug(order[i]);
}

Compilation message (stderr)

currencies.cpp:109:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  109 | main(){
      | ^~~~

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