Submission #1307244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307244		kian2009	Two Currencies (JOI23_currencies)	C++20	100 / 100	1140 ms	41192 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10, MAXBIT = 19;

ll n, m, q, cnt = 1, x[MAXN], y[MAXN], s[MAXN], t[MAXN], fen[MAXN];
int h[MAXN], par[MAXN], dp[MAXN][MAXBIT], st[MAXN], ed[MAXN], c[MAXN];
int l[MAXN], r[MAXN];
vector<int> adj[MAXN], q1[MAXN];
pair<int, int> e[MAXN];
vector<pair<int, pair<int, int>>> w;

void input() {
	cin >> n >> m >> q;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		adj[--u].push_back(--v);
		adj[v].push_back(u);
		e[i] = {u, v};
	}
	for (int i = 0; i < m; i++) {
		ll x, w1;
		cin >> x >> w1;
		--x;
		w.push_back({w1, {e[x].first, e[x].second}});
	}
	for (int i = 0; i < q; i++) {
		cin >> s[i] >> t[i] >> x[i] >> y[i];
		--s[i];
		--t[i];	
	}
	sort(w.begin(), w.end());
}

void calcDp(int u) {
	dp[u][0] = par[u];
	for (int i = 1; i < MAXBIT; i++)
		dp[u][i] = dp[dp[u][i - 1]][i - 1];
}

void dfs1(int u, int p) {
	st[u] = cnt++;
	par[u] = p;
	calcDp(u);
	for (auto v : adj[u])
		if (v != p) {
			h[v] = h[u] + 1;
			dfs1(v, u);
		}
	ed[u] = cnt;
}

int up(int u, int d) {
	int res = u;
	for (int i = 0; i < MAXBIT; i++)
		if ((d >> i) & 1)
			res = dp[res][i];
	return res;	
}

int lca(int u, int v) {
	if (h[u] > h[v])
		swap(u, v);
	v = up(v, h[v] - h[u]);
	if (u == v)
		return u;
	for (int i = MAXBIT - 1; i >= 0; i--)
		if (dp[u][i] != dp[v][i]) {
			u = dp[u][i];
			v = dp[v][i];
		}
	return par[u];
}

void upd(int u, int x) {
	for (; u < MAXN; u += u & -u)
		fen[u] += x;	
}

ll get(int u) {
	ll res = 0;
	for (; u; u -= u & -u)
		res += fen[u];
	return res;	
}

void calcAns() {
	for (int i = 0; i < q; i++) {
		l[i] = -1;
		r[i] = m;	
	}
	for (int i = 0; i < MAXBIT; i++) {
		for (int j = 0; j < q; j++)
			if ((r[j] - l[j]) > 1)
				q1[(l[j] + r[j]) / 2].push_back(j);
		for (int j = 0; j < m; j++) {
			int u = w[j].second.first, v = w[j].second.second;
			if (h[u] < h[v])
				swap(u, v);
			upd(st[u], w[j].first);
			upd(ed[u], -w[j].first);
			for (auto f : q1[j]) {
				int l1 = lca(s[f], t[f]);
				ll sum = get(st[s[f]]) + get(st[t[f]]) - 2 * get(st[l1]);
				if (sum <= y[f])
					l[f] = j;
				else
					r[f] = j;
			}
		}
		for (int j = 0; j < m; j++)
			q1[j].clear();
		memset(fen, 0, sizeof(fen));
	}
}

void findAns() {
	for (int i = 0; i < q; i++)
		if (l[i] != -1)
			q1[l[i]].push_back(i);
	for (int i = 0; i < m; i++) {
		int u = w[i].second.first, v = w[i].second.second;
		if (h[u] < h[v])
			swap(u, v);
		upd(st[u], 1);
		upd(ed[u], -1);
		for (auto f : q1[i]) {
			int l1 = lca(s[f], t[f]);
			c[f] = get(st[s[f]]) + get(st[t[f]]) - 2 * get(st[l1]);	
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	input();
	dfs1(0, 0);
	calcAns();
	findAns();
	for (int i = 0; i < q; i++) {
		int sum = get(st[s[i]]) + get(st[t[i]]) - 2 * get(st[lca(s[i], t[i])]) - c[i];
		cout << (sum > x[i]? -1: x[i] - sum) << '\n';	
	}
	return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void input()':
currencies.cpp:28:30: warning: narrowing conversion of 'w1' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   28 |                 w.push_back({w1, {e[x].first, e[x].second}});
      |                              ^~

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