Submission #854729

#	Time	Username	Problem	Language	Result	Execution time	Memory
854729		serifefedartar	Two Currencies (JOI23_currencies)	C++17	100 / 100	380 ms	39848 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 18; 
const ll MAXN = 1e5 + 5;
 
struct Query {
	int from, to;
	ll gold, silver;
	int low;
	Query(int a, int b, ll c, ll d) : from(a), to(b), gold(c), silver(d) { }
};
 
vector<vector<int>> graph;
vector<pair<int,int>> edges;
vector<pair<ll,int>> cost;
vector<Query> queries;
int depth[MAXN], up[LOGN][MAXN], cnt[MAXN], counter[MAXN];
int tin[MAXN], tout[MAXN], mx_silver[MAXN], ans[MAXN];
ll fen[MAXN], fen2[MAXN];
int T = 0;
 
void dfs(int node, int parent) {
	tin[node] = ++T;
	for (auto u : graph[node]) {
		if (u == parent)
			continue;
 
		depth[u] = depth[node] + 1;
		up[0][u] = node;
		for (int i = 1; i < LOGN; i++)
			up[i][u] = up[i-1][up[i-1][u]];
		dfs(u, node);
	}
	tout[node] = T;
}
 
void dfs2(int node, int parent) {
	counter[node] = counter[parent] + cnt[node];
	for (auto u : graph[node]) {
		if (u == parent)
			continue;
		dfs2(u, node);
	}
}
 
int find(int node, int k) {
	for (int i = 0; i < LOGN; i++) {
		if ((1<<i) & k)
			node = up[i][node];
	}
	return node;
}
 
int lca(int a, int b) {
	if (depth[b] > depth[a])
		swap(a, b);
	a = find(a, depth[a] - depth[b]);
	if (a == b)
		return a;
 
	for (int i = LOGN-1; i >= 0; i--) {
		if (up[i][a] != up[i][b]) {
			a = up[i][a];
			b = up[i][b];
		}
	}
	return up[0][a];
}
 
void update(int k, ll val) {
	while (k < MAXN) {
		fen[k] += val;
		if (val > 0)
			fen2[k]++;
		else if (val < 0)
			fen2[k]--;
		k += k & -k;
	}
}
 
void range(int l, int r, ll val) {
	update(l, val);
	update(r+1, -val);
}
 
ll get(int k) {
	k = tin[k];
	ll res = 0; 
	while (k) {
		res += fen[k];
		k -= k & -k;
	}
	return res;
}
 
int get2(int k) {
	k = tin[k];
	int res = 0;
	while (k) {
		res += fen2[k];
		k -= k & -k;
	}
	return res;
}
 
void parallel(ll l, ll r, vector<int> qs) {
	if (l > r || qs.size() == 0)
		return ;
	if (l == r) {
		int node = cost[l-1].s;
		ll C = cost[l-1].f;
		range(tin[node], tout[node], C);
		for (auto u : qs) {
			Query qry = queries[u];
			ll total_silver = get(qry.from) + get(qry.to) - 2 * get(qry.low);
			if (total_silver <= qry.silver)
				ans[u] = get2(qry.from) + get2(qry.to) - 2 * get2(qry.low);
		}
		range(tin[node], tout[node], -C);
		return ; 
	}
 
 
	int mid = l + (r-l)/2;
	for (ll i = l; i <= mid; i++) {
		int node = cost[i-1].s;
		ll C = cost[i-1].f;
		range(tin[node], tout[node], C);
	}
 
	vector<int> left, right;
	for (auto u : qs) {
		Query qry = queries[u];
		ll total_silver = get(qry.from) + get(qry.to) - 2 * get(qry.low);
		if (total_silver <= qry.silver) {
			right.push_back(u);
			ans[u] = get2(qry.from) + get2(qry.to) - 2 * get2(qry.low);
		} else
			left.push_back(u);
	}
 
	parallel(mid+1, r, right);
	for (int i = mid; i >= l; i--) {
		int node = cost[i-1].s;
		ll C = cost[i-1].f;
		range(tin[node], tout[node], -C);
	}
	parallel(l, mid, left);
}
 
int main() {
	fast
	int N, M, Q, u, v;
	cin >> N >> M >> Q;
 
	graph = vector<vector<int>>(N+1, vector<int>());
	for (int i = 1; i < N; i++) {
		cin >> u >> v;
		edges.push_back({u, v});
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	for (int i = 0; i < LOGN; i++)
		up[i][1] = 1;
	dfs(1, 1);
 
	for (int i = 0; i < M; i++) {
		ll P, C;
		cin >> P >> C;
		int edge = (depth[edges[P-1].f] > depth[edges[P-1].s] ? edges[P-1].f : edges[P-1].s);
		cnt[edge]++;
		cost.push_back({C, edge});
	}
	sort(cost.begin(), cost.end());
	dfs2(1, 1);
 
	for (int i = 0; i < Q; i++) {
		ll a, b, c, d;
		cin >> a >> b >> c >> d;
		queries.push_back(Query(a, b, c, d));
		queries.back().low = lca(queries.back().from, queries.back().to);
	}
 
	vector<int> qs;
	for (int i = 0; i < Q; i++)
		qs.push_back(i);
 
	parallel(1, cost.size(), qs);
 
	for (int i = 0; i < Q; i++) {
		int all = counter[queries[i].from] + counter[queries[i].to] - 2 * counter[queries[i].low];
		int can_be_silver = ans[i];
		if (all-can_be_silver > queries[i].gold)
			cout << "-1\n";
		else
			cout << queries[i].gold - all + can_be_silver << "\n";
	}
}

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