Submission #731771

#	Time	Username	Problem	Language	Result	Execution time	Memory
731771		jk410	Two Currencies (JOI23_currencies)	C++17	100 / 100	3037 ms	36932 KiB

currencies

#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define pb push_back
#define ll long long
using namespace std;
struct segmentTree {
	vector<ll> tree;
	void init(int n) {
		tree.clear();
		tree.resize(1 << (int)ceil(log2(n)) + 1);
	}
	void update(int lx, int rx, ll v, int l, int r, int n) {
		if (r < lx || rx < l)
			return;
		if (lx <= l && r <= rx) {
			tree[n] += v;
			return;
		}
		int m = (l + r) >> 1;
		update(lx, rx, v, l, m, n << 1);
		update(lx, rx, v, m + 1, r, n << 1 | 1);
	}
	ll query(int x, int l, int r, int n) {
		if (r < x || x < l)
			return 0;
		if (l == r)
			return tree[n];
		int m = (l + r) >> 1;
		return query(x, l, m, n << 1) + query(x, m + 1, r, n << 1 | 1) + tree[n];
	}
};
struct query {
	int s, t;
	ll x, y;
};
int N, M, Q;
vector<int> Adj[100000];
pair<int, int> Edges[100000];
pair<ll, int> CP[100000];
query Queries[100000];
int In[100000], Out[100000];
int Par[17][100000];
int Depth[100000];
int QL[100000], QR[100000], QX[100000];
segmentTree ST;
ll Ans[100000];
int dfs(int v, int par, int cur) {
	In[v] = ++cur;
	for (int i : Adj[v]) {
		if (i != par)
			cur = dfs(i, v, cur);
	}
	return Out[In[v]] = cur;
}
int getLCA(int u, int v) {
	if (Depth[u] > Depth[v])
		swap(u, v);
	for (int i = 0, t = Depth[v] - Depth[u]; t; i++, t >>= 1) {
		if (t & 1)
			v = Par[i][v];
	}
	if (u == v)
		return u;
	for (int i = 16; i >= 0; i--) {
		if (Par[i][u] != Par[i][v]) {
			u = Par[i][u];
			v = Par[i][v];
		}
	}
	return Par[0][u];
}
ll pathQuery(int u, int v) {
	int lca = getLCA(u, v);
	return ST.query(u, 0, N - 1, 1) + ST.query(v, 0, N - 1, 1) - 2 * ST.query(lca, 0, N - 1, 1);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> Q;
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		Edges[i] = { --a,--b };
		Adj[a].pb(b);
		Adj[b].pb(a);
	}
	for (int i = 0; i < M; i++) {
		int p;
		ll c;
		cin >> p >> c;
		CP[i] = { c,--p };
	}
	sort(CP, CP + M);
	for (int i = 0; i < Q; i++) {
		int s, t;
		ll x, y;
		cin >> s >> t >> x >> y;
		Queries[i] = { --s,--t,x,y };
	}
	dfs(0, -1, -1);
	for (int i = 0; i < N - 1; i++) {
		pair<int, int>& cur = Edges[i];
		cur.first = In[cur.first];
		cur.second = In[cur.second];
		if (cur.first > cur.second)
			swap(cur.first, cur.second);
		Par[0][cur.second] = cur.first;
	}
	for (int i = 1; i < N; i++)
		Depth[i] = Depth[Par[0][i]] + 1;
	for (int i = 0; i < Q; i++) {
		query& cur = Queries[i];
		cur.s = In[cur.s];
		cur.t = In[cur.t];
	}
	for (int i = 1; i < 17; i++) {
		for (int j = 0; j < N; j++)
			Par[i][j] = Par[i - 1][Par[i - 1][j]];
	}
	fill(QR, QR + Q, M);
	while (1) {
		bool flag = true;
		vector<pair<int, int>> v;
		for (int i = 0; i < Q; i++) {
			if (QL[i] <= QR[i]) {
				flag = false;
				v.pb({ (QL[i] + QR[i]) >> 1,i });
			}
		}
		if (flag)
			break;
		sort(all(v));
		ST.init(N);
		for (int i = 0, j = 0; i <= M; i++) {
			if (i) {
				int cur = Edges[CP[i - 1].second].second;
				ll c = CP[i - 1].first;
				ST.update(cur, Out[cur], c, 0, N - 1, 1);
			}
			while (j < (int)v.size() && v[j].first == i) {
				int cur = v[j++].second;
				if (pathQuery(Queries[cur].s, Queries[cur].t) <= Queries[cur].y) {
					QX[cur] = i;
					QL[cur] = i + 1;
				}
				else
					QR[cur] = i - 1;
			}
		}
	}
	vector<pair<int, int>> v;
	for (int i = 0; i < Q; i++)
		v.push_back({ QX[i],i });
	sort(all(v));
	ST.init(N);
	for (int i = 0, j = 0; i <= M; i++) {
		if (i) {
			int cur = Edges[CP[i - 1].second].second;
			ST.update(cur, Out[cur], 1, 0, N - 1, 1);
		}
		while (j < (int)v.size() && v[j].first == i) {
			int cur = v[j++].second;
			Ans[cur] = pathQuery(Queries[cur].s, Queries[cur].t);
		}
	}
	for (int i = 0; i < Q; i++)
		cout << max(Queries[i].x - pathQuery(Queries[i].s, Queries[i].t) + Ans[i], (ll)-1) << "\n";
	return 0;
}

Compilation message (stderr)

currencies.cpp: In member function 'void segmentTree::init(int)':
currencies.cpp:10:39: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   10 |   tree.resize(1 << (int)ceil(log2(n)) + 1);
      |                    ~~~~~~~~~~~~~~~~~~~^~~

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