Submission #1297604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297604		KickingKun	Two Currencies (JOI23_currencies)	C++20	0 / 100	4 ms	4416 KiB

currencies

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

#define ll long long
#define ull unsigned long long
#define ld long double
#define bigint __int128
#define emb emplace_back
#define pb push_back
#define pii pair <int, int>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define Task ""

#define MASK(k) (1ull << k)
#define bitcnt(k) __builtin_popcount(k)
#define testBit(n, k) ((n >> k) & 1)
#define flipBit(n, k) (n ^ (1ll << k))
#define offBit(n, k) (n & ~MASK(k))
#define onBit(n, k) (n | (1ll << k))

template <class T> bool minimize(T &a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool maximize(T &a, T b) {if (a < b) {a = b; return true;} return false;}

const int N = 1e5 + 5, LG = 17, mod = 1e9 + 7;
const ll INF = 1e18;

struct FenwickTree {
	vector <ll> bit;
	FenwickTree (int len) {
		bit.assign(len + 1, 0);
	}

	void resize(int len) {
		bit.assign(len + 1, 0);
	}

	void update(int p, int val) {
		for (; p < bit.size(); p += p & -p)
			bit[p] += val;
	}

	ll get(int p) {
		ll res = 0; for (; p > 0; p -= p & -p) res += bit[p];
		return res;
	}
};

int n, m, q, par[N], h[N];
int st[N], en[N], up[N][LG], dfsTimes = 0;
pii edge[N];
vector <int> adj[N];

struct Query {
	int u, v, x, y; pii range;
	int cntSilver, checkPoints;
	int lca;
} query[N];

void dfs(int u, int p = -1) {
	st[u] = ++dfsTimes;
	for (int v: adj[u]) if (v != p) {
		par[v] = up[v][0] = u; h[v] = h[u] + 1;
		for (int i = 1; i < LG; i++)
			up[v][i] = up[up[v][i - 1]][i - 1];
		dfs(v, u);
	}
	en[u] = ++dfsTimes;
}

int lca(int u, int v) {
	if (h[u] != h[v]) {
		if (h[u] < h[v]) swap(u, v);
		for (int i = 0, k = h[u] - h[v]; (1 << i) <= k; i++)
			if (testBit(k, i)) u = up[u][i];
	}
	if (u == v) return u;
	for (int i = __lg(h[u]); i > -1; i--)
		if (up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
	return up[u][0];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	if (fopen(Task".inp", "r")) {
		freopen(Task".inp", "r", stdin);
		freopen(Task".out", "w", stdout);
	}

	cin >> n >> m >> q;
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
		edge[i] = make_pair(u, v);
	}

	vector <pii> checkPoints;
	for (int i = 1; i <= m; i++) {
		int p, c; cin >> p >> c;
		checkPoints.emplace_back(c, p);
	}
	sort (all(checkPoints));

	for (int i = 1; i <= q; i++) {
		cin >> query[i].u >> query[i].v >> query[i].x >> query[i].y;
	}

	dfs(1);

	for (int i = 1; i < n; i++) {
		if (par[edge[i].fi] == edge[i].se) 
			swap(edge[i].fi, edge[i].se);
		// edge[i] = make_pair(p, u)
	}

	FenwickTree fenCnt(2 * n), fenSum(2 * n);
	for (auto [silver, e]: checkPoints) {
		auto [p, u] = edge[e];
		fenCnt.update(st[u], 1);
		fenCnt.update(en[u], -1);
	}
	for (int i = 1; i <= q; i++) {
		int u = query[i].u, v = query[i].v;
		query[i].lca = lca(query[i].u, query[i].v);
		query[i].range = make_pair(-1, checkPoints.size() - 1);
		query[i].checkPoints = fenCnt.get(st[u]) + fenCnt.get(st[v]) - 2 * fenCnt.get(st[query[i].lca]);
		query[i].cntSilver = 0;
	}

	while (true) {
		vector <pii> events;
		for (int i = 1; i <= q; i++) if (query[i].range.fi != query[i].range.se) {
			int mid = (query[i].range.fi + query[i].range.se + 1) >> 1;
			events.emplace_back(mid, i);
		}

		if (events.empty()) break;
		sort (all(events));

		int p = -1; fenSum.resize(2 * n), fenCnt.resize(2 * n);
		for (auto [k, id]: events) {
			while (p < k) {
				auto [silver, e] = checkPoints[++p];
				auto [p, u] = edge[e];
				fenSum.update(st[u], silver);
				fenSum.update(en[u], -silver);
				fenCnt.update(st[u], 1);
				fenCnt.update(en[u], -1);
			}

			int u = query[id].u, v = query[id].v;
			ll silverCoins = fenSum.get(st[u]) + fenSum.get(st[v]) - 2 * fenSum.get(st[query[id].lca]);
			if (silverCoins <= query[id].y) {
				query[id].range.fi = k;
				query[id].cntSilver = fenCnt.get(st[u]) + fenCnt.get(st[v]) - 2 * fenCnt.get(st[query[id].lca]);
			}
			else query[id].range.se = k - 1;
		}
	}

	for (int i = 1; i <= q; i++) {
		int useGold = query[i].checkPoints - query[i].cntSilver;
		int ans = query[i].x - useGold;
		if (ans < 0) ans = -1;
		cout << ans << '\n';
	}
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:88:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |                 freopen(Task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:89:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |                 freopen(Task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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