Submission #796755

#	Time	Username	Problem	Language	Result	Execution time	Memory
796755		GusterGoose27	Two Currencies (JOI23_currencies)	C++17	100 / 100	626 ms	133920 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int MAXN = 1e5+5;
const int MAXB = 17;
int n, m, q;

vector<pii> edges[MAXN];
vector<int> at_edge[MAXN];
int cost[MAXN];
int pos[MAXN];
int lca[MAXN][MAXB];
int depth[MAXN];

class stree {
public:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	ll sum = 0;
	int num = 0;
	stree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp < rp) {
			int mid = (lp+rp)/2;
			l = new stree(lp, mid);
			r = new stree(mid+1, rp);
		}
	}
	stree(stree *prev, int v) {
		assert(!prev->l);
		sum = prev->sum+v;
		num = prev->num+1;
		lp = prev->lp;
		rp = prev->rp;
	}
	stree(stree *l, stree *r) : l(l), r(r) {
		sum = l->sum+r->sum;
		num = l->num+r->num;
		lp = l->lp;
		rp = r->rp;
	}
	stree *upd(int p, int v) {
		if (lp > p || rp < p) return this;
		if (lp == rp) return new stree(this, v);
		return new stree(l->upd(p, v), r->upd(p, v));
	}
};

stree *trees[MAXN];

void dfs(int cur, int p = -1) {
	for (pii e: edges[cur]) {
		int nxt = e.first;
		if (nxt == p) continue;
		trees[nxt] = trees[cur];
		for (int v: at_edge[e.second]) {
			trees[nxt] = trees[nxt]->upd(pos[v], cost[v]);
		}
		lca[nxt][0] = cur;
		depth[nxt] = 1+depth[cur];
		dfs(nxt, cur);
	}
}

int get_lca(int s, int t) {
	if (depth[s] < depth[t]) swap(s, t);
	for (int i = MAXB-1; i >= 0 && depth[s] > depth[t]; i--) {
		if ((1<<i) <= depth[s]-depth[t]) s = lca[s][i];
	}
	if (s == t) return s;
	for (int i = MAXB-1; i >= 0; i--) {
		if (lca[s][i] != lca[t][i]) {
			s = lca[s][i];
			t = lca[t][i];
		}
	}
	assert(s != t);
	assert(lca[s][0] == lca[t][0]);
	return lca[s][0];
}

int walk(stree *a, stree *b, stree *c, ll &amt) { // return max num you can buy with this amt
	if (amt == 0) return 0;
	if (a->sum+b->sum-2*c->sum <= amt) {
		amt -= (a->sum+b->sum-2*c->sum);
		return (a->num+b->num-2*c->num);
	}
	else if (!a->l) {
		amt = 0;
		return 0;
	}
	int v = walk(a->l, b->l, c->l, amt);
	return v + walk(a->r, b->r, c->r, amt);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m >> q;
	for (int i = 0; i < n-1; i++) {
		int x, y; cin >> x >> y; x--; y--;
		edges[x].push_back(pii(y, i));
		edges[y].push_back(pii(x, i));
	}
	vector<pii> sortable;
	for (int i = 0; i < m; i++) {
		int p, w; cin >> p >> w;
		p--;
		at_edge[p].push_back(i);
		cost[i] = w;
		sortable.push_back(pii(w, i));
	}
	sort(sortable.begin(), sortable.end());
	for (int i = 0; i < m; i++) pos[sortable[i].second] = i;
	trees[0] = new stree(0, m-1);
	dfs(0);
	for (int j = 1; j < MAXB; j++) {
		for (int i = 0; i < n; i++) lca[i][j] = lca[lca[i][j-1]][j-1];
	}
	for (int i = 0; i < q; i++) {
		int s, t, x; ll y; cin >> s >> t >> x >> y;
		s--; t--;
		int l = get_lca(s, t);
		int rem = trees[s]->num+trees[t]->num-2*trees[l]->num-walk(trees[s], trees[t], trees[l], y);
		if (rem <= x) cout << x-rem << '\n';
		else cout << "-1\n";
	}
}

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