Submission #1209518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209518		duckindog	Two Currencies (JOI23_currencies)	C++17	100 / 100	991 ms	44984 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 100'000 + 10;
int n, m, q;
pair<int, int> edge[N];
struct CP { 
	int p, c;
	friend istream& operator >> (istream& is, CP& rhs) { 
		return is >> rhs.p >> rhs.c;
	}
} cp[N];
struct Query { 
	int s, t, x, y;
	friend istream& operator >> (istream& is, Query& rhs) { 
		return is >> rhs.s >> rhs.t >> rhs.x >> rhs.y;
	}
} query[N];

vector<int> ad[N];

int f[N][17];
int st[N], ed[N], num;
void dfs(int u, int p = -1) { 
	st[u] = ++num;

	for (int i = 1; i <= 16; ++i) f[u][i] = f[f[u][i - 1]][i - 1];
	for (const auto& v : ad[u]) { 
		if (v == p) continue;
		f[v][0] = u;
		dfs(v, u);
	}

	ed[u] = num;
}
inline bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }
int lca(int u, int v) { 
	if (anc(u, v)) return u;
	if (anc(v, u)) return v;
	
	for (int i = 16; i >= 0; --i)
		if (!anc(f[u][i], v)) u = f[u][i];
	return f[u][0];
}

vector<int> allC;
vector<int> save[N];

struct BIT { 
	long long bit[N];
	void upd(int i, int x) { 
		for (; i <= n; i += i & -i) bit[i] += x;
	}
	int que(int i) { 
		long long ret = 0;
		for (; i; i -= i & -i) ret += bit[i];
		return ret;
	}

	void upd(int l, int r, int x) { 
		upd(l, x);
		upd(r + 1, -x);
	}
} T, D, F, Total;

int answer[N];
void dnc(int l, int r, vector<int>& Qlist) { 
	if (!Qlist.size()) return;
	int mid = (l + r) >> 1;
	
	for (int i = l; i <= mid; ++i) { 
		for (const auto& idx : save[i]) { 
			const auto& [u, v] = edge[idx];
			T.upd(st[v], ed[v], allC[i]);
			F.upd(st[v], ed[v], 1);
			if (i == mid) D.upd(st[v], ed[v], 1);
		}
	}
	
	array<vector<int>, 2> nxt;
	for (const auto& idx : Qlist) { 
		auto [s, t, x, y] = query[idx];
		
		int LCA = lca(s, t);
		int total = T.que(st[s]) + T.que(st[t]) - 2 * T.que(st[LCA]),
			cnt = D.que(st[s]) + D.que(st[t]) - 2 * D.que(st[LCA]),
			useCnt = F.que(st[s]) + F.que(st[t]) - 2 * F.que(st[LCA]),
			totalCnt = Total.que(st[s]) + Total.que(st[t]) - 2 * Total.que(st[LCA]);
		total -= 1ll * allC[mid] * cnt;
		useCnt -= cnt;
		
		if (y < total) { 
			nxt[0].push_back(idx);
			continue;
		}
		y -= total;
		
		int cntAdd = y / allC[mid];
		useCnt += min(cnt, cntAdd);
		if (x < totalCnt - useCnt) { 
			nxt[1].push_back(idx);
			continue;
		}
		nxt[1].push_back(idx);
			
		answer[idx] = x - (totalCnt - useCnt);
	}
	
	for (const auto& idx : save[mid]) { 
		const auto& [u, v] = edge[idx];
		D.upd(st[v], ed[v], -1);
	}
	
	if (l != r) dnc(mid + 1, r, nxt[1]);

	for (int i = l; i <= mid; ++i) { 
		for (const auto& idx : save[i]) { 
			const auto& [u, v] = edge[idx];
			T.upd(st[v], ed[v], -allC[i]);
			F.upd(st[v], ed[v], -1);
		}
	}

	if (l != r) dnc(l, mid, nxt[0]);
}

int32_t main() { 
	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> m >> q;
	for (int i = 1; i < n; ++i) cin >> edge[i].first >> edge[i].second;
	for (int i = 1; i <= m; ++i) cin >> cp[i];
	for (int i = 1; i <= q; ++i) cin >> query[i];

	for (int i = 1; i < n; ++i) { 
		const auto& [u, v] = edge[i];
		ad[u].push_back(v);
		ad[v].push_back(u);
	}
	dfs(f[1][0] = 1);

	for (int i = 1; i < n; ++i) { 
		auto& [u, v] = edge[i];
		if (anc(v, u)) swap(u, v);
	}
	{ // discrete
		for (int i = 1; i <= m; ++i) allC.push_back(cp[i].c);
		sort(allC.begin(), allC.end());
		allC.erase(unique(allC.begin(), allC.end()), allC.end());

		for (int i = 1; i <= m; ++i) { 
			auto it = upper_bound(allC.begin(), allC.end(), cp[i].c) - allC.begin();
			save[it].push_back(cp[i].p);
		}
		allC.insert(allC.begin(), 0);
	}	

	for (int i = 1; i <= m; ++i) {
		const auto& [p, c] = cp[i];
		int v = edge[p].second;
		Total.upd(st[v], ed[v], 1);
	}
	
	fill(answer + 1, answer + q + 1, -1);
	vector<int> Qlist(q); iota(Qlist.begin(), Qlist.end(), 1);
	dnc(1, allC.size() - 1, Qlist);

	for (int i = 1; i <= q; ++i) cout << answer[i] << "\n";
}

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