Submission #1308235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308235		pvb.tunglam	Two Currencies (JOI23_currencies)	C++20	100 / 100	1104 ms	43788 KiB

currencies

#include <bits/stdc++.h>
#define pw2(i) (1LL << (i))
#define all(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;

	  /*------------- I alone decide my fate ! -------------*/
/*------ We wish you a Merry Christmas and a happy new year! ------*/

int N, M, Q, res[100009];
struct query {
	int s, t, x;
	ll y;
} q[100009];
pair <int, int> edge[1000009], tram[100009];
vector <int> adj[100009];
int tin[100009], tout[100009], timeDFS = 0;
int lef[100009], righ[100009], up[100009][18], dep[100009], lca[100009];
vector <int> inQ[100009];

void DFS(int u, int p) {
	tin[u] = ++timeDFS;
	for (auto v : adj[u]) {
		if (v == p) continue;
		up[v][0] = u;
		dep[v] = dep[u] + 1;
		for (int i = 1; i <= 17; i ++) {
			up[v][i] = up[up[v][i - 1]][i - 1];
		}
		DFS(v, u);
	}
	tout[u] = timeDFS;
}

int getlca(int a, int b) {
	if (dep[a] < dep[b]) swap(a, b);
	int len = dep[a] - dep[b];
	for (int i = 0; i <= 17; i ++) {
		if ((len >> i) & 1) {
			a =up[a][i];
		}
	}
	if (a == b) return a;
	for (int i = 17; i >= 0; i --) {
		if (up[a][i] != up[b][i]) {
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
	
}

struct Fenwick{
	int n;
	vector <ll> bit;
	vector <pair <int, int> > undo;
	void init(int _n) {
		n = _n;
		bit.resize(n + 9, 0);
	}
	void update(int x, int val, bool keep) {
		if (keep) undo.push_back({x, -val});
		while (x <= n) {
			bit[x] += val;
			x += x &- x;
		}
	}
	ll get(int x) {
		ll ret = 0;
		while (x) {
			ret += bit[x];
			x -= x &- x;
		}
		return ret;
	}
	void reset() {
		while (!undo.empty()) {
			update(undo.back().first, undo.back().second, 0);
			undo.pop_back();
		}
	}
} fenCnt, fenSum;

void solve() {
	cin >> N >> M >> Q;
	for (int i = 1; i < N; i ++) {
		int u, v; cin >> u >> v;
		edge[i] = {u, v};
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1; i <= M; i ++) {
		cin >> tram[i].first >> tram[i].second;
	}
	sort(tram + 1, tram + M + 1, [] (pair <int, int> a, pair <int, int> b) {
		return a.second < b.second;
	});
	
	DFS(1, 0);
	for (int i = 1; i <= M; i ++) {
		int idx = tram[i].first;
		if (tin[edge[idx].first] > tin[edge[idx].second]) {
			swap(edge[idx].first, edge[idx].second);
		}
	}
	for (int i = 1; i <= Q; i ++) {
		lef[i] = 1; righ[i] = M;
		cin >> q[i].s >> q[i].t >> q[i].x >> q[i].y;
		lca[i] = getlca(q[i].s, q[i].t);
	}
	bool loop = 1;
	fenCnt.init(N);
	fenSum.init(N);
	
	while (loop) {
		loop = 0;
		for (int i = 1; i <= Q; i ++) {
			if (lef[i] > righ[i]) continue;
			loop = 1;
			int mid = (lef[i] + righ[i]) >> 1;
			inQ[mid].push_back(i);
		}
		for (int i = 1; i <= M; i ++) {
			int idx = tram[i].first;
			int child = edge[idx].second;   
			fenCnt.update(tin[child], 1, 1);
			fenCnt.update(tout[child] + 1, -1, 1);
			fenSum.update(tin[child], tram[i].second, 1);
			fenSum.update(tout[child] + 1, -tram[i].second, 1);

			for (auto j : inQ[i]) {
				int s = q[j].s, t = q[j].t;
				int cnt = fenCnt.get(tin[s]) + fenCnt.get(tin[t]) - 2 * fenCnt.get(tin[lca[j]]);
				ll sum = fenSum.get(tin[s]) + fenSum.get(tin[t]) - 2 * fenSum.get(tin[lca[j]]);
				if (q[j].y >= sum) {
					lef[j] = i + 1;
					res[j] =  cnt;
				}
				else righ[j] = i - 1;
			}
			inQ[i].clear();
		}
		fenCnt.reset(); fenSum.reset();	
	}
	
	for (int i = 1; i <= M; ++i) {
	    int idx = tram[i].first;
	    int child = edge[idx].second;
	    fenCnt.update(tin[child], 1, 0);
	    fenCnt.update(tout[child] + 1, -1, 0);
	}
	vector<int> totalChk(Q+1);
	for (int i = 1; i <= Q; ++i) {
	    int s = q[i].s, t = q[i].t, l = lca[i];
	    totalChk[i] = fenCnt.get(tin[s]) + fenCnt.get(tin[t]) - 2 * fenCnt.get(tin[l]);
	}

	for (int i = 1; i <= Q; ++i) {
	    int t = totalChk[i];
	    int s = res[i];
	    int goldNeeded = t - s;
	    if (goldNeeded > q[i].x) cout << -1 << '\n';
	    else cout << q[i].x - goldNeeded << '\n';
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr); cout.tie(nullptr);
	solve();
	return 0;
}

/*
  How can you see into my eyes, like open doors?
  Leading you down into my core, where I've become so numb
  Without a soul, my spirit's sleeping somewhere cold
  Until you find it here and bring it back home!
  Wake me up! Wake me up inside
  Can't wake up? Wake me up inside
*/

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