Submission #1261581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261581		4QT0R	Two Currencies (JOI23_currencies)	C++20	28 / 100	119 ms	27824 KiB

currencies

/*
Podzadanie: wszystkie c_i równe

Zliczamy, ile jest bramek na ścieżce drzewem przedziałowym jak we wzorcówce.
*/

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const int II = 1'000'000'000;
const ll I = 1'000'000'000'000'000'000LL;
const int K = 17;
const int N = 1 << K;

pair<int, int> e[N];
vector<int> ed[N];
int jp[N][K + 1];
int pos[N], pre[N], cnt = 0;

ll drz[2 * N];

pair<ll, ll> il[N];
int v1[N], v2[N], l[N];
int poc[N], kon[N];
ll akt[N];
pair<int, int> que[N];

pair<int, int> dod[N];

ll answer[N];

void Add(int a, int b, ll x)
{
	a += N - 1;
	b += N + 1;
	while (a / 2 != b / 2)
	{
		if (a % 2 == 0)
			drz[a + 1] += x;
		if (b % 2 == 1)
			drz[b - 1] += x;
		a /= 2;
		b /= 2;
	}
}

ll Sum(int v)
{
	ll ans = 0LL;
	v += N;
	while (v > 0)
	{
		ans += drz[v];
		v /= 2;
	}
	return ans;
}

void DFS(int v)
{
	++cnt;
	pre[v] = cnt;
	pos[v] = cnt;
	for (int i = 1; i <= K; ++i)
		jp[v][i] = jp[jp[v][i - 1]][i - 1];
	for (int i = 0; i < (int)ed[v].size(); ++i)
	{
		if (pre[ed[v][i]])
			continue;
		jp[ed[v][i]][0] = v;
		DFS(ed[v][i]);
		pos[v] = pos[ed[v][i]];
	}
}

int LCA(int a, int b)
{
	if (pre[a] > pre[b])
		swap(a, b);
	for (int i = K; i >= 0; --i)
		if (pos[jp[a][i]] < pre[b])
			a = jp[a][i];
	if (pos[a] < pre[b])
		a = jp[a][0];
	return a;
}

void Solve()
{
	int n, m, q, a, b;
	ll cost;
	cin >> n >> m >> q;
	for (int i = 1; i < n; ++i)
	{
		cin >> a >> b;
		e[i] = pair{a, b};
		ed[a].pb(b);
		ed[b].pb(a);
	}
	jp[1][0] = 1;
	DFS(1);

	for (int i = 1; i <= m; ++i)
	{
		cin >> a >> cost;
		if (jp[e[a].st][0] == e[a].nd)
			a = e[a].st;
		else
			a = e[a].nd;
		Add(pre[a],pos[a],1);
	}
	for (int i = 1; i <= q; ++i)
	{
		cin >> v1[i] >> v2[i] >> il[i].st >> il[i].nd;
		l[i] = LCA(v1[i], v2[i]);
		ll gates = max(0ll, Sum(pre[v1[i]]) + Sum(pre[v2[i]]) - 2*Sum(pre[l[i]]) - il[i].nd/cost);
		if (gates > il[i].st)cout << "-1\n";
		else cout << il[i].st - gates << '\n';
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Solve();

	return 0;
}

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