Submission #1281803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281803		AbdullahIshfaq	Two Currencies (JOI23_currencies)	C++20	10 / 100	189 ms	53304 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
const int N = 100010, lg = 20;
ll n, m, k, x[N], y[N], a[N], ccol[N], ts[4 * N], tc[4 * N], tl[4 * N], trt[4 * N], roots[N], cc = 0, p[N][lg], h[N];
vector<ll> g[N], g2[N];
vector<vector<ll>> col;
int update(int u, int id, int l = 0, int r = m)
{
	if (id < l || r <= id)
		return u;
	cc++;
	ll xx = cc;
	ts[xx] = ts[u];
	tc[xx] = tc[u];
	tl[xx] = tl[u];
	trt[xx] = trt[u];
	ts[xx] += col[id][0];
	tc[xx] += 1;
	if (r - l == 1)
		return xx;
	ll m = (l + r) / 2;
	tl[xx] = update(tl[xx], id, l, m);
	trt[xx] = update(trt[xx], id, m, r);
	return xx;
}
int query(int r1, int r2, int r3, ll s, int l = 0, int r = m)
{
	if (tc[r2] + tc[r3] - 2 * tc[r1] <= 1)
	{
		return (s < ts[r2] + ts[r3] - 2 * ts[r1]) ? 1 : 0;
	}
	ll m = (l + r) / 2;
	if (ts[tl[r2]] + ts[tl[r3]] - 2 * ts[tl[r1]] > s)
	{
		return query(tl[r1], tl[r2], tl[r3], s, l, m) + tc[trt[r2]] + tc[trt[r3]] - 2 * tc[trt[r1]];
	}
	else
	{
		return query(trt[r1], trt[r2], trt[r3], s - (ts[tl[r2]] + ts[tl[r3]] - 2 * ts[tl[r1]]), m, r);
	}
}
void dfs(int u, int par)
{
	p[u][0] = par;
	roots[u] = roots[par];
	for (auto i : g2[u])
	{
		if (x[a[i]] == par or y[a[i]] == par)
		{
			roots[u] = update(roots[u], ccol[i]);
		}
	}
	for (auto i : g[u])
	{
		if (i != par)
		{
			h[i] = h[u] + 1;
			dfs(i, u);
		}
	}
}
int lca(int x1, int y1)
{
	if (h[x1] > h[y1])
		swap(x1, y1);
	ll d = h[y1] - h[x1];
	for (int i = 0; i < lg; i++)
	{
		if ((1ll << i) & d)
			y1 = p[y1][i];
	}
	if (x1 == y1)
		return x1;
	for (int i = lg - 1; i >= 0; i--)
	{
		if (p[x1][i] != p[y1][i])
		{
			x1 = p[x1][i];
			y1 = p[y1][i];
		}
	}
	return p[x1][0];
}
void solve()
{
	cin >> n >> m >> k;
	for (int i = 1; i < n; i++)
	{
		cin >> x[i] >> y[i];
		g[x[i]].push_back(y[i]);
		g[y[i]].push_back(x[i]);
	}
	for (int i = 1; i <= m; i++)
	{
		cin >> a[i] >> ccol[i];
		col.push_back({ccol[i], i});
		g2[x[a[i]]].push_back(i);
		g2[y[a[i]]].push_back(i);
	}
	sort(col.begin(), col.end());
	for (int i = 0; i < m; i++)
	{
		ccol[col[i][1]] = i;
	}
	roots[0] = 0;
	dfs(1, 0);
	for (int j = 1; j < lg; j++)
	{
		for (int i = 1; i <= n; i++)
		{
			p[i][j] = p[p[i][j - 1]][j - 1];
		}
	}
	for (int i = 0; i < k; i++)
	{
		ll s, e, gl, sl;
		cin >> s >> e >> gl >> sl;
		ll z = lca(s, e);
		cout << max(gl - query(roots[z], roots[s], roots[e], sl), -1ll) << '\n';
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int tests = 1;
	// cin >> tests;
	for (int i = 1; i <= tests; i++)
	{
		// cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}

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