Submission #903981

#	Time	Username	Problem	Language	Result	Execution time	Memory
903981		Trisanu_Das	Two Currencies (JOI23_currencies)	C++17	100 / 100	819 ms	81180 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
 
const int Z = 1e5, INF = 1e18;
 
struct BIT {
	int *a, n;
	void init(int N) {
		a = new int[(n = N) + 1] {};
	}
	void add(int i, int v) {
		for(++i; i <= n; i += i&-i) a[i] += v;
	}
	int get(int i) {
		int v =  0;
		for(++i; i >= 1; i -= i&-i) v += a[i];
		return v;
	}
};
 
int N, M, Q, p[Z], lca[Z], eL[Z], eR[Z], dfsTimer, ans[Z];
vector<int> g[Z];
vector<array<int, 2>> o;
set<int> s[Z];
array<int, 4> q[Z];
BIT b[2] {};
 
void dfs0(int u) {
	eL[u] = dfsTimer++;
	for(int v : g[u]) if(v != p[u]) {
		p[v] = u, dfs0(v);
		if(size(s[v]) > size(s[u])) swap(s[u], s[v]);
		for(int i : s[v]) {
			if(s[u].find(i) == end(s[u])) s[u].insert(i);
			else {
				lca[i] = u;
				s[u].erase(i);
			}
		}
	}
 
	eR[u] = dfsTimer++;
}
 
void add(int i, int u, int v) {
	b[i].add(eL[u], +v);
	b[i].add(eR[u], -v);
}
 
void modify(int i, int f) {
	add(0, o[i][1], o[i][0] * f);
	add(1, o[i][1], -f);
}
 
int calc(int i) {
	array<int, 2> val;
	for(int j : {0, 1}) val[j] = b[j].get(eL[q[i][0]]) + b[j].get(eL[q[i][1]]) - 2 * b[j].get(eL[lca[i]]);
	if(val[0] <= q[i][3]) return q[i][2] - val[1];
	else return -INF;
}
 
void dfs1(int l, int r, vector<int> &qry) {
	if(r - l < 2 || empty(qry)) {
		for(int i = l; i < r; ++i) modify(i, +1);
		for(int i : qry) ans[i] = calc(i);
		if(!l && r == 1) {
			modify(0, -1);
			for(int i : qry) if(ans[i] == -INF) ans[i] = calc(i);
			modify(0, +1);
		}
		return;
	}
	int m = (l + r) / 2;
	for(int i = l; i <= m; ++i)	modify(i, +1);
	vector<int> qv[2];
	for(int i : qry) qv[calc(i) > -INF].push_back(i);
	for(int i = l; i <= m; ++i)	modify(i, -1);
	dfs1(l, m, qv[0]);
	dfs1(m, r, qv[1]);
}
 
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> M >> Q;
	array<int, 2> edges[N-1], temp[M];
	for(auto &[u, v] : edges) {
		cin >> u >> v; --u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(auto &[i, w] : temp) cin >> i >> w, --i;
	for(int i = 0; i < Q; ++i) {
		cin >> q[i][0] >> q[i][1] >> q[i][2] >> q[i][3];
		for(int j : {0, 1}) s[--q[i][j]].insert(i);
	}
	dfs0(0);
	for(auto &[i, w] : temp) {
		int u = edges[i][p[edges[i][1]] == edges[i][0]];
		o.push_back({w, u});
	}
	for(int i : {0, 1}) b[i].init(2*N);
	sort(begin(o), end(o));
	for(auto [w, u] : o) add(1, u, 1);
	vector<int> qv(Q);
	iota(begin(qv), end(qv), 0);
	dfs1(0, size(o), qv);
	for(int i = 0; i < Q; ++i) cout << max(ans[i], (int)-1) << '\n';
}

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