Submission #918848

#	Time	Username	Problem	Language	Result	Execution time	Memory
918848		42kangaroo	Two Currencies (JOI23_currencies)	C++17	100 / 100	2992 ms	160948 KiB

currencies

//
// Created by 42kangaroo on 26/01/2024.
//
#include "bits/stdc++.h"

using namespace std;

#define int long long

using g_t = vector<vector<int>>;

struct SegAb {
	int st, en, se;
};

struct Node {
	int l, r, bl, br, numL, sumL;
};

struct PSegTe {
	vector<Node> a;
	vector<int> cooC;
	int high;

	int build(int l, int r) {
		int act = a.size();
		a.push_back({-1, -1, l, r, 0, 0});
		if (l + 1 < r) {
			int m = (l + r) / 2;
			a[act].l = build(l, m);
			a[act].r = build(m, r);
		}
		return act;
	}

	pair<int, int> get(int st, int k) {
		if (a[st].br <= k) return {a[st].numL, a[st].sumL};
		if (a[st].bl >= k) return {0, 0};
		pair<int, int> res = {0, 0};
		if (a[st].l != -1) {
			auto re = get(a[st].l, k);
			res.first += re.first;
			res.second += re.second;
			re = get(a[st].r, k);
			res.first += re.first;
			res.second += re.second;
		}
		return res;
	}

	int add(int st, int k, int v) {
		if (a[st].bl > k || a[st].br <= k) return st;
		int nN = a.size();
		a.push_back({-1, -1, a[st].bl, a[st].br, 0, 0});
		if (a[st].l != -1) {
			a[nN].l = add(a[st].l, k, v);
			a[nN].r = add(a[st].r, k, v);
			a[nN].numL = a[a[nN].l].numL + a[a[nN].r].numL;
			a[nN].sumL = a[a[nN].l].sumL + a[a[nN].r].sumL;
		} else {
			a[nN].numL = a[st].numL + 1;
			a[nN].sumL = a[st].sumL + v;
		}
		return nN;
	}
};

int dfs(int n, int p, int d, g_t &g, vector<int> &pa, vector<int> &de) {
	de[n] = d;
	int su = 1;
	int ma = 0;
	pa[n] = p;
	for (auto &e: g[n]) {
		if (e == p) continue;
		int re = dfs(e, n, d + 1, g, pa, de);
		su += re;
		if (re > ma) {
			swap(e, g[n][0]);
			ma = re;
		}
	}
	return su;
}

void segDfs(int n, int p, int seg, g_t &g, vector<PSegTe> &segs, vector<int> &segThis, g_t &cos) {
	segThis[n] = seg;
	if (seg == -1) {
		segThis[n] = segs.size();
		segs.push_back({{}, {}, n});
	}
	for (auto e: cos[n]) {
		segs[segThis[n]].cooC.push_back(e);
	}
	bool first = true;
	for (auto e: g[n]) {
		if (e == p) continue;
		if (first) {
			segDfs(e, n, segThis[n], g, segs, segThis, cos);
			first = false;
		} else {
			segDfs(e, n, -1, g, segs, segThis, cos);
		}
	}
}

void initSegDfs(int n, int p, int st, g_t &g, vector<PSegTe> &segs,
                vector<int> &segThis, vector<int> &topSeg, g_t &cos) {
	topSeg[n] = st;
	for (auto e: cos[n]) {
		topSeg[n] = segs[segThis[n]].add(topSeg[n], std::lower_bound(segs[segThis[n]].cooC.begin(),
		                                                           segs[segThis[n]].cooC.end(), e) -
		                                          segs[segThis[n]].cooC.begin(), e);
	}
	bool first = true;
	for (auto e: g[n]) {
		if (e == p) continue;
		if (first) {
			initSegDfs(e, n, topSeg[n], g, segs, segThis, topSeg, cos);
			first = false;
		} else {
			initSegDfs(e, n, 0, g, segs, segThis, topSeg, cos);
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, q;
	cin >> n >> m >> q;
	vector<pair<int, int>> edge(n - 1);
	g_t g(n);
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		g[a].push_back(b);
		g[b].push_back(a);
		edge[i] = {a, b};
	}
	vector<int> p(n);
	vector<int> d(n);
	dfs(0, 0, 0, g, p, d);
	for (int i = 0; i < n - 1; ++i) {
		if (p[edge[i].first] != edge[i].second) swap(edge[i].first, edge[i].second);
	}
	g_t cos(n);
	int cs = -1;
	for (int i = 0; i < m; ++i) {
		int pj, c;
		cin >> pj >> c;
		cs = c;
		pj--;
		cos[edge[pj].first].push_back(c);
	}
	vector<PSegTe> segs;
	vector<int> segThis(n);
	segDfs(0, 0, -1, g, segs, segThis, cos);
	for (auto &seg: segs) {
		std::sort(seg.cooC.begin(), seg.cooC.end());
		seg.cooC.erase(std::unique(seg.cooC.begin(), seg.cooC.end()), seg.cooC.end());
		seg.build(0, seg.cooC.size());
	}
	vector<int> topSeg(n);
	initSegDfs(0, 0, 0, g, segs, segThis, topSeg, cos);
	for (int i = 0; i < q; ++i) {
		int a, b, gol, sil;
		cin >> a >> b >> gol >> sil;
		--a;
		--b;
		vector<SegAb> abs;
		while (segThis[a] != segThis[b]) {
			if (d[segs[segThis[a]].high] < d[segs[segThis[b]].high]) swap(a, b);
			abs.push_back({a, -1, segThis[a]});
			a = p[segs[segThis[a]].high];
		}
		if (d[a] < d[b]) swap(a, b);
		if (a != b) {
			abs.push_back({a, b, segThis[a]});
		}
		int numChe = 0;
		for (auto &e: abs) {
			numChe += segs[e.se].a[topSeg[e.st]].numL;
			if (e.en != -1) {
				numChe -= segs[e.se].a[topSeg[e.en]].numL;
			}
		}
		int l = 0, r = 1e9 + 1;
		while (l + 1 < r) {
			m = (l + r) / 2;
			int su = 0;
			for (auto &e: abs) {
				int k = std::upper_bound(segs[e.se].cooC.begin(), segs[e.se].cooC.end(), m) - segs[e.se].cooC.begin();
				su += segs[e.se].get(topSeg[e.st], k).second;
				if (e.en != -1) {
					su -= segs[e.se].get(topSeg[e.en], k).second;
				}
			}
			if (su >= sil) r = m;
			else l = m;
		}
		int su = 0;
		int nuS = 0;
		for (auto &e: abs) {
			int k = std::upper_bound(segs[e.se].cooC.begin(), segs[e.se].cooC.end(), r) - segs[e.se].cooC.begin();
			auto res = segs[e.se].get(topSeg[e.st], k);
			su += res.second;
			nuS += res.first;
			if (e.en != -1) {
				res = segs[e.se].get(topSeg[e.en], k);
				su -= res.second;
				nuS -= res.first;
			}
		}
		int dif = su - sil;
		nuS -= (dif + r - 1)/r;
		numChe -= nuS;
		numChe = max(0ll, numChe);
		if (gol - numChe < -1) numChe = gol + 1;
		cout << gol - numChe << "\n";
	}
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:148:6: warning: variable 'cs' set but not used [-Wunused-but-set-variable]
  148 |  int cs = -1;
      |      ^~

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