Submission #1047495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047495		ymm	Two Currencies (JOI23_currencies)	C++17	100 / 100	1750 ms	555968 KiB

currencies

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

pll operator+(const pll &a, const pll &b) {
	return { a.first + b.first, a.second + b.second };
}

class Seg {
private:
	struct Node {
		Node *l, *r;
		pll val;

		int cl, cr;
		pll cv;

		static Node *nw() {
			static Node pool[(1<<29)/sizeof(Node)];
			static int p = 0;
			return &pool[p++];
		}
	};
	vector<Node *> roots = {0};
	vector<ll> tags;
	int begin, end;

	pll get(Node *t, int l, int r, int b, int e) {
		if (r <= b || e <= l || !t)
			return {};
		if (l <= b && e <= r)
			return t->val;
		if (l == t->cl && r == t->cr)
			return t->cv;
		t->cl = l;
		t->cr = r;
		return t->cv = get(t->l, l, r, b, (b+e)/2) + get(t->r, l, r, (b+e)/2, e);
	}

	Node *add(Node *t, int p, const pll &x, int b, int e) {
		Node *ans = Node::nw();
		ans->val = t? t->val + x: x;
		if (e - b > 1) {
			if (p < (b + e)/2) {
				ans->l = add(t? t->l: 0, p, x, b, (b+e)/2);
				ans->r = t? t->r: 0;
			} else {
				ans->l = t? t->l: 0;
				ans->r = add(t? t->r: 0, p, x, (b+e)/2, e);
			}
		}
		return ans;
	}

public:
	Seg(int l, int r) : begin(l), end(r) {}

	void add(int p, const pll &x, ll tag) {
		roots.push_back(add(roots.back(), p, x, begin, end));
		tags.push_back(tag);
	}

	pll get_lower_bound(int l, int r, ll tag) {
		int p = lower_bound(tags.begin(), tags.end(), tag) - tags.begin();
		return get(roots[p], l, r, begin, end);
	}
};

const int N = 100'010;

struct Node {
	vector<Node *> adj;
	Node *par;
	Node *hroot, *hleaf, *hchild;
	Seg *hseg;
	int h;
	int sz;
} graph[N];

ostream &operator<<(ostream &o, Node *v) {
	o << "N";
	if (v)
		o << v - graph;
	else
		o << "(nil)";
	return o;
}

void dfs1(Node *v, Node *p, int h)
{
	v->sz = 1;
	v->h = h;
	v->par = p;
	for (auto u : v->adj) {
		if (u == p)
			continue;
		dfs1(u, v, h + 1);
		if (!v->hchild || v->hchild->sz < u->sz)
			v->hchild = u;
	}
}

void dfs2(Node *v, Node *hroot)
{
	hroot->hleaf = v;
	v->hroot = hroot;
	for (auto u : v->adj) {
		if (u == v->par)
			continue;
		dfs2(u, v->hchild == u? hroot: u);
	}
	if (hroot == v)
		v->hseg = new Seg(v->h, v->hleaf->h + 1);
}

Node *lower(Node *v, Node *u) {
	return v->h > u->h? v: u;
}

void add_checkpoint(Node *v, pll x, ll tag)
{
	v->hroot->hseg->add(v->h, x, tag);
}

class QueryCache : public vector<tuple<Seg *, int, int>> {
public:
	pll query(ll tag) {
		pll sum = {};
		for (auto [s, l, r] : *this)
			sum = sum + s->get_lower_bound(l, r, tag);
		return sum;
	}
};

QueryCache get_seg_ranges(Node *v, Node *u)
{
	QueryCache ans;
	while (v->hroot != u->hroot) {
		if (v->hroot->h < u->hroot->h)
			swap(v, u);
		ans.emplace_back(v->hroot->hseg, v->hroot->h, v->h + 1);
		v = v->hroot->par;
	}
	if (v->h < u->h)
		swap(v, u);
	ans.emplace_back(v->hroot->hseg, u->h + 1, v->h + 1);
	return ans;
}

vector<pair<Node *, Node *>> edges;
struct Checkpoint {
	Node *v, *u;
	ll s;

	bool operator<(const Checkpoint &other) { return s < other.s; };
};
vector<Checkpoint> checkpoints;
const ll inf = 1.01e18;

ll solve(Node *v, Node *u, ll gold, ll silver)
{
	int l = 0, r = checkpoints.size();
	QueryCache qc = get_seg_ranges(v, u);
	while (l < r) {
		int m = (l + r + 1)/2;
		if (qc.query(m).first > silver)
			r = m-1;
		else
			l = m;
	}
	ll ans = gold - (qc.query(checkpoints.size()).second - qc.query(l).second);
	if (ans < 0)
		ans = -1;
	return ans;
}

void make_hls()
{
	dfs1(graph, 0, 0);
	dfs2(graph, graph);
	sort(checkpoints.begin(), checkpoints.end());
	Loop (i,0,checkpoints.size()) {
		auto &c = checkpoints[i];
		add_checkpoint(lower(c.v, c.u), {c.s, 1}, i);
	}
}

Node *read_node() { int i; cin >> i; return graph + i - 1; }

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, m, q;
	cin >> n >> m >> q;
	Loop (i,0,n-1) {
		auto v = read_node();
		auto u = read_node();
		edges.emplace_back(v, u);
		v->adj.push_back(u);
		u->adj.push_back(v);
	}
	Loop (i,0,m) {
		int p;
		ll s;
		cin >> p >> s;
		checkpoints.push_back((Checkpoint){
				.v = edges[p-1].first,
				.u = edges[p-1].second,
				.s = s,
		});
	}
	make_hls();
	while (q--) {
		auto v = read_node();
		auto u = read_node();
		ll gold, silver;
		cin >> gold >> silver;
		cout << solve(v, u, gold, silver) << '\n';
	}
}

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