Submission #789616

#	Time	Username	Problem	Language	Result	Execution time	Memory
789616		hugo_pm	Two Currencies (JOI23_currencies)	C++17	100 / 100	1829 ms	283932 KiB

currencies

// Begin hl/core.hpp
#pragma once
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using v32 = vector<int>;
using v64 = vector<ll>;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
const int m197 = 1000000007;
const int m998 = 998244353;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, a, b) for(int i = (a); i < (b); i++)

template<typename T>
void chmax(T &x, const T &v) { if (x < v) x = v; }
template<typename T>
void chmin(T &x, const T &v) { if (x > v) x = v; }
template<typename T>
int len(const T &x) { return (int)(x.size()); }

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
	cout << ' ' << H;
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type
operator<<(Ostream& os,  const Cont& v){
	os << "[";
	for (auto &x : v) os << x << ", ";
	return os << "]";
}

template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p) {
	return os << "{" << p.first << ", " << p.second << "}";
}

template<int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
	static_assert(D >= 1, "Vector dimension must be greater than zero!");
	template<typename... Args>
		Vec(int n, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {}
};

template<typename T>
struct Vec<1, T> : public vector<T> {
	Vec(int n, const T& val = T()) : vector<T>(n, val) {}
};

template<class Fun>
class letrec_result {
	Fun fun_;
public:
	template<class T>
		explicit letrec_result(T &&fun): fun_(std::forward<T>(fun)) {}

	template<class ...Args>
		decltype(auto) operator()(Args &&...args) {
			return fun_(ref(*this), std::forward<Args>(args)...);
		}
};

template<class Fun>
decltype(auto) letrec(Fun &&fun) {
	return letrec_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

ll nxt() { ll x; cin >> x; return x; }
template<typename T>
vector<T> read_vector(int n) {
	vector<T> v(n);
	for (T &x : v) cin >> x;
	return v;
}
vector<int> rv32(int n) { return read_vector<int>(n); }
vector<ll> rv64(int n) { return read_vector<ll>(n); }

template<typename T>
void print_vector(vector<T> data, bool print_size, bool new_line) {
	int n = data.size();
	if (print_size) cout << n << '\n';
	for (int i = 0; i < n; ++i) cout << data[i] << " \n"[i+1 == n || new_line];
}

void fastio() {
	ios::sync_with_stdio(false), cin.tie(0);
}

vector<int> az_to_int(string s) {
	vector<int> ret(s.size());
	rep(i, 0, (int)s.size()) ret[i] = s[i] - 'a';
	return ret;
}
// End hl/core.hpp
// Begin hl/data/usual.hpp
#pragma once
// Begin hl/data/segtree.hpp
#pragma once
#include <vector>

template<class node, node (*op)(node, node), node (*e)()>
class segtree {
public:
	segtree(std::vector<node> v) : _n(v.size()), log(0) {
		while ((1 << log) < _n) {
			++log;
		}

		size = (1 << log);
		data.assign(2*size, e());

		for (int i = 0; i < _n; ++i) {
			data[size+i] = v[i];
		}

		for (int i = size-1; i >= 1; --i) {
			update(i);
		}
	}

	segtree(int t = 0, node x = e()) : segtree(std::vector<node>(t, x)) { }

	node get(int pos) {
		return data[size+pos];
	}

	void set(int pos, node val) {
		pos += size;
		data[pos] = val;
		for (int i = 1; i <= log; ++i) {
			update(pos >> i);
		}
	}

	void refresh(int pos, node proposal) {
		set(pos, op(data[size+pos], proposal));
	}

	node query_semi_open(int left, int right) {
		left += size;
		right += size;
		node res_left = e(), res_right = e(); 

		while (left < right) {
			if (left & 1) {
				res_left = op(res_left, data[left++]);
			}
			if (right & 1) {
				res_right = op(data[--right], res_right);
			}
			left >>= 1, right >>= 1;	
		}

		return op(res_left, res_right);
	}

	node query_all() {
		return data[1];
	}

private:
	int _n, log, size;
	std::vector<node> data;

	void update(int k) {
		data[k] = op(data[k<<1], data[k<<1|1]);
	}
};
// End hl/data/segtree.hpp
// Begin hl/data/lazy_segtree.hpp
#pragma once
#include <vector>
#include <cassert>

template<class node,
node (*op)(node, node),
node (*e)(),
class fun,
node (*eval)(fun, node),
fun (*composition)(fun, fun),
fun (*id)()>
class lazy_segtree {
public:
	lazy_segtree(std::vector<node> v) : _n(v.size()), log(0) {
		while ((1 << log) < _n) {
			++log;
		}

		size = (1 << log);
		data.assign(2*size, e());
		lazy.assign(size, id());

		for (int i = 0; i < _n; ++i) {
			data[size + i] = v[i];
		}

		for (int i = size-1; i >= 1; --i) {
			update_one(i);
		}
	}

	lazy_segtree(int t = 0, node x = e()) : lazy_segtree(std::vector<node>(t, x)) { }

	node get(int pos) {
		int leaf = pos + size;
		push_anc(leaf);
		return data[leaf];
	}

	void set(int pos, node val) {
		int leaf = pos + size;
		push_anc(leaf);
		data[leaf] = val;
		update_anc(leaf);
	}

	node query_semi_open(int left, int right) {
		left += size;
		right += size;
		node res_left = e(), res_right = e();

		push_anc(left, left);
		push_anc(right, right);

		while (left < right) {
			if (left & 1) {
				res_left = op(res_left, data[left++]);
			}
			if (right & 1) {
				res_right = op(data[--right], res_right);
			}
			left >>= 1;
			right >>= 1;	
		}

		return op(res_left, res_right);
	}

	node query_all() {
		return data[1];
	}

	void apply_one(int pos, fun fct) {
		int leaf = pos + size;
		push_anc(leaf);
		data[leaf] = eval(fct, data[leaf]);
		update_anc(leaf);
	}

	void apply_semi_open(int left, int right, fun fct) {
		left += size;
		right += size;

		if (left == right) {
			return;
		}

		push_anc(left, left);
		push_anc(right - 1, right);

		int old_left = left, old_right = right;
		while (left < right) {
			if (left & 1) {
				all_apply(left++, fct);
			}
			if (right & 1) {
				all_apply(--right, fct);
			}
			left >>= 1;
			right >>= 1;
		}

		left = old_left, right = old_right;
		update_anc(left, left);
		update_anc(right - 1, right);
	}

private:
	int _n, log, size;
	std::vector<node> data;
	std::vector<fun> lazy;

	void update_one(int k) {
		data[k] = op(data[k << 1], data[k << 1 | 1]);
	}

	void update_anc(int leaf, int dev = 1) {
		int s = 1 + __builtin_ctz(dev);
		for (int i = s; i <= log; ++i) {
			update_one(leaf >> i);
		}
	}

	void all_apply(int k, fun fct) {
		data[k] = eval(fct, data[k]);
		if (k < size) {
			lazy[k] = composition(fct, lazy[k]);
		}
	}

	void push_one(int k) {
		all_apply(k << 1, lazy[k]);
		all_apply(k << 1 | 1, lazy[k]);
		lazy[k] = id();
	}

	void push_anc(int leaf, int dev = 1) {
		int s = 1 + __builtin_ctz(dev);
		for (int i = log; i >= s; --i) {
			push_one(leaf >> i);
		}
	}
};
// End hl/data/lazy_segtree.hpp
#include <optional>
using ll = long long;

template<typename T, const T BIG_>
struct numeric_segtree {
	static constexpr T BIG = BIG_;
	static T fct_sum(T a, T b) { return a + b; }
	static T e_sum() { return 0; }

	static T fct_min(T a, T b) { return (a < b ? a : b); }
	static T e_min() { return BIG; }

	static T fct_max(T a, T b) { return (a > b ? a : b); }
	static T e_max() { return -BIG; }

	using segtree_min = segtree<T, fct_min, e_min>;
	using segtree_max = segtree<T, fct_max, e_max>;
	using segtree_sum = segtree<T, fct_sum, e_sum>;

	using lazy_min_add = lazy_segtree<T, fct_min, e_min, T, fct_sum, fct_sum, e_sum>;
	using lazy_max_add = lazy_segtree<T, fct_max, e_max, T, fct_sum, fct_sum, e_sum>;
	using lazy_sum_add = lazy_segtree<T, fct_sum, e_sum, T, fct_sum, fct_sum, e_sum>;

	using set_struct = std::optional<T>;
	static set_struct comp_set(set_struct f1, set_struct f2) {
		return (f1 ? f1 : f2);
	}
	static T eval_set(set_struct fct, T val) {
		return (fct ? *fct : val);
	}
	static set_struct e_set() {
		return std::nullopt;
	}

	using lazy_min_set = lazy_segtree<T, fct_min, e_min, set_struct, eval_set, comp_set, e_set>;
	using lazy_max_set = lazy_segtree<T, fct_max, e_max, set_struct, eval_set, comp_set, e_set>;
	using lazy_sum_set = lazy_segtree<T, fct_sum, e_sum, set_struct, eval_set, comp_set, e_set>;
};

using usual32 = numeric_segtree<int, (int)1e9>;
using usual64 = numeric_segtree<long long, (ll)3e18>;

// End hl/data/usual.hpp
#define int long long

using pii = pair<int, int>;
using vi = vector<int>;
const int INF = 3e18;
pii opmin(pii a, pii b) {
    return min(a, b);
}
pii e_min() { return {INF, -1}; }
using SegSum = usual64::segtree_sum;
using SegMin = segtree<pii, opmin, e_min>;

struct PathSumEdge {
	vector<vi> adj;
	int N;
	int ordCnt = 0;
	vector<pii> begEnd;
	vector<pii> passages;
	vector<int> firstPass;
	vector<int> depth;
	SegMin lca_tree;
	SegSum sum_tree;

	void dfs(int node, int anc) {
		begEnd[node].first = ordCnt++;
		firstPass[node]= passages.size();
		passages.emplace_back(depth[node], node);
		for(auto voisin : adj[node]) if (voisin != anc) {
			depth[voisin] = depth[node]+1;
			dfs(voisin, node);
			passages.emplace_back(depth[node], node);
		}
		begEnd[node].second = ordCnt++;
	}

	void resetSum() {
		sum_tree = SegSum(2*N, 0);
	}

	PathSumEdge(int _N, vector<vi> _adj) :
	adj(_adj), N(_N), begEnd(_N), firstPass(_N), depth(_N) {
		assert(N == (int)adj.size());
		dfs(0, -1);
		lca_tree = SegMin(passages);
		resetSum();
	}

	void edgeAdd(int u, int v, int delta) {
		if (depth[u] > depth[v]) swap(u, v);
		// u parent, v child
		sum_tree.refresh(begEnd[v].first, delta);
		sum_tree.refresh(begEnd[v].second, -delta);
	}

	int edgePathSum(int u, int v) {
		if(firstPass[u] > firstPass[v]){
			swap(u, v);
		}
		int lca = lca_tree.query_semi_open(firstPass[u], firstPass[v]+1).second;
		int res = 0;
		// (lca, u/v]
		for (int x : {u, v})
			res += sum_tree.query_semi_open(begEnd[lca].first+1, begEnd[x].first+1);
		return res;
	}
};

struct Query {
	int id;
	// gold = initial - tout
	int S, T, gold, silver;
	// [lo, hi] : nombre de silverables
	int lo, hi;
	int mid() { return lo + (hi-lo+1)/2; }
};
signed main() {
	fastio();
	int nbNode = nxt(), nbChk = nxt(), nbReq = nxt();
	vector<vi> adj(nbNode);
	vector<pii> edges;
	rep(iEdge, 0, nbNode-1) {
		int u = nxt()-1, v = nxt()-1;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edges.emplace_back(u, v);
	}
	PathSumEdge ps(nbNode, adj);
	vector<pair<int, pii>> checkpoints;
	rep(iChk, 0, nbChk) {
		int iEdge = nxt()-1, bonus = nxt();
		checkpoints.emplace_back(bonus, edges[iEdge]);
		// calcul nombre de chk
		ps.edgeAdd(edges[iEdge].first, edges[iEdge].second, 1);
	}
	sort(all(checkpoints));
	vector<vector<Query>> done(nbChk+1);
	int nbDone = 0;
	vector<vector<Query>> _empty(nbChk+1);
	auto todo = _empty;
	auto push = [&] (Query &r) {
		if (r.lo == r.hi) {
			done[r.mid()].push_back(r); ++nbDone;
		} else {
			todo[r.mid()].push_back(r);
		}
	};
	rep(iReq, 0, nbReq) {
		Query r;
		r.id = iReq;
		cin >> r.S >> r.T >> r.gold >> r.silver;
		--r.S; --r.T;
		r.gold -= ps.edgePathSum(r.S, r.T);
		r.lo = 0, r.hi = nbChk;
		push(r);
	}
	vector<vector<Query>> old;
	while (nbDone < nbReq) {
		old = todo;
		todo = _empty;
		ps.resetSum();
		rep(taken, 1, nbChk+1) {
			auto [bonus, edge] = checkpoints[taken-1];
			auto [u, v] = edge;
			ps.edgeAdd(u, v, bonus);
			for (Query r : old[taken]) {
				if (r.silver < ps.edgePathSum(r.S, r.T)) {
					r.hi = taken-1;
				} else {
					r.lo = taken;
				}
				push(r);
			}
		}
	}
	vector<int> answers(nbReq);
	ps.resetSum();
	rep(taken, 0, nbChk+1) {
		for (Query r : done[taken]) {
			answers[r.id] = max(-1LL, r.gold + ps.edgePathSum(r.S, r.T));
		}
		if (taken < nbChk) {
			auto [u, v] = checkpoints[taken].second;
			ps.edgeAdd(u, v, 1);
		}
	}
	rep(iReq, 0, nbReq) {
		cout << answers[iReq] << '\n';
	}
}

Compilation message (stderr)

currencies.cpp:2:9: warning: #pragma once in main file
    2 | #pragma once
      |         ^~~~
currencies.cpp:109:9: warning: #pragma once in main file
  109 | #pragma once
      |         ^~~~
currencies.cpp:111:9: warning: #pragma once in main file
  111 | #pragma once
      |         ^~~~
currencies.cpp:184:9: warning: #pragma once in main file
  184 | #pragma once
      |         ^~~~

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