Submission #740933

#	Time	Username	Problem	Language	Result	Execution time	Memory
740933		pavement	Two Currencies (JOI23_currencies)	C++17	100 / 100	2370 ms	59952 KiB

currencies

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, M, Q, idx, A[100005], B[100005], P[100005], C[100005], S[100005], T[100005], U[100005], X[100005], Y[100005], lo[100005], hi[100005], pre[100005], sz[100005], dep[100005], ckpt[100005], anc[25][100005];
bool can[100005];
ii ft[100005];
iii ans[100005];
vector<int> adj[100005];
map<int, vector<int> > add, ask;

int dfs(int n, int e = -1) {
	for (int k = 1; k <= 20; k++) {
		if (anc[k - 1][n] == -1) break;
		anc[k][n] = anc[k - 1][anc[k - 1][n]];
	}
	pre[n] = ++idx;
	sz[n] = 1;
	for (auto u : adj[n]) if (u != e) {
		dep[u] = dep[n] + 1;
		anc[0][u] = n;
		sz[n] += dfs(u, n);
	}
	return sz[n];
}

int lca(int u, int v) {
	if (dep[u] > dep[v]) swap(u, v);
	for (int k = 20; k >= 0; k--) {
		if (dep[v] - (1 << k) >= dep[u]) {
			v = anc[k][v];
		}
	}
	if (u == v) return u;
	for (int k = 20; k >= 0; k--) {
		if (anc[k][u] != anc[k][v]) {
			u = anc[k][u];
			v = anc[k][v];
		}
	}
	return anc[0][u];
}

int ls(int x) { return x & -x; }

ii qry(int p) {
	ii ret = mp(0, 0);
	for (; p; p -= ls(p)) {
		ret.first += ft[p].first;
		ret.second += ft[p].second;
	}
	return ret;
}

void upd(int l, int r, ii v) {
	for (; l <= N; l += ls(l)) {
		ft[l].first += v.first;
		ft[l].second += v.second;
	}
	for (r++; r <= N; r += ls(r)) {
		ft[r].first -= v.first;
		ft[r].second -= v.second;
	}
}

main() {
	memset(anc, -1, sizeof anc);
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	cin >> N >> M >> Q;
	for (int i = 1; i < N; i++) {
		cin >> A[i] >> B[i];
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
	}
	dfs(1);
	for (int i = 1; i <= M; i++) {
		cin >> P[i] >> C[i];
		if (dep[A[P[i]]] < dep[B[P[i]]]) P[i] = B[P[i]];
		else P[i] = A[P[i]];
	}
	for (int i = 1; i <= Q; i++) {
		cin >> S[i] >> T[i] >> X[i] >> Y[i];
		lo[i] = 1;
		hi[i] = (int)1e9;
		U[i] = lca(S[i], T[i]);
	}
	for (int rep = 0; rep < 30; rep++) {
		vector<ii> ev;
		for (int i = 1; i <= N; i++) {
			ft[i] = mp(0, 0);
		}
		for (int i = 1; i <= Q; i++) {
			can[i] = 0;
			int mid = (lo[i] + hi[i]) / 2;
			ev.eb(mid, i);
		}
		for (int i = 1; i <= M; i++) {
			ev.eb(C[i], -i);
		}
		sort(ev.begin(), ev.end());
		for (auto [v, idx] : ev) {
			if (idx < 0) {
				idx = -idx;
				upd(pre[P[idx]], pre[P[idx]] + sz[P[idx]] - 1, mp(v, 1ll));
			} else {
				auto r1 = qry(pre[S[idx]]);
				auto r2 = qry(pre[T[idx]]);
				auto r3 = qry(pre[U[idx]]);
				auto r = mp(r1.first + r2.first - 2 * r3.first, r1.second + r2.second - 2 * r3.second);
				if (r.first <= Y[idx]) {
					can[idx] = 1;
					g0(ans[idx]) = r.first;
					g1(ans[idx]) = r.second;
				}
			}
		}
		for (int i = 1; i <= Q; i++) {
			int mid = (lo[i] + hi[i]) / 2;
			if (can[i]) {
				g2(ans[i]) = mid;
				lo[i] = mid + 1;
			} else {
				hi[i] = mid - 1;
			}
		}
	}
	for (int i = 1; i <= Q; i++) {
		auto r1 = qry(pre[S[i]]);
		auto r2 = qry(pre[T[i]]);
		auto r3 = qry(pre[U[i]]);
		auto r = mp(r1.first + r2.first - 2 * r3.first, r1.second + r2.second - 2 * r3.second);
		ckpt[i] = r.second;
		auto [a, b, c] = ans[i];
		if (c == (int)1e9) continue;
		//~ cout << i << ' ' << a << ' ' << b << ' ' << c << ' ' << S[i] << ' ' << T[i] << ' ' << U[i] << '\n';
		int extra = (Y[i] - a) / (c + 1);
		g0(ans[i]) += extra * (c + 1);
		g1(ans[i]) += extra;
	}
	for (int i = 1; i <= Q; i++) {
		auto [x, y, z] = ans[i];
		cout << max(-1ll, X[i] - (ckpt[i] - y)) << '\n';
		//~ cout << X[i] << ' ' <<  x << ' ' << y << ' ' << z << ' ' << ckpt[i] << '\n';
	}
}

Compilation message (stderr)

currencies.cpp:89:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   89 | main() {
      | ^~~~

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