Submission #1036595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036595		0npata	Two Currencies (JOI23_currencies)	C++17	38 / 100	2171 ms	1048576 KiB

currencies

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

#define int long long
#define vec vector

const int N = 1<<17;
const int CMX = (int)1<<31;

struct Node {
	int cnt = 0;
	int sum = 0;

	Node* left = nullptr;
	Node* right = nullptr;

	Node* get_right() {
		if(right == nullptr) {
			right = new Node{};
		}
		return right;
	}
	Node* get_left() {
		if(left == nullptr) {
			left = new Node{};
		}
		return left;
	}

	void insert(int val, int l = 0, int r = CMX) {
		cnt++;
		sum += val;
		if(l+1 == r) return;
		int m = (l+r)/2;
		if(val >= m) {
			get_right()->insert(val, m, r);
		}
		else {
			get_left()->insert(val, l, m);
		}
	}

	~Node() {
		delete left;
		delete right;
	}
};

Node roots[N*3];

void insert(int i, int val) {
	i += N;
	roots[i].insert(val);
	while(i > 1) {
		i /= 2;
		roots[i].insert(val);
	}
}

int tree_sz[N];
int ri[N];

int t = 0;
int depth[N];

vec<int> tree[N];
int par[N];

void dfs1(int u = 0, int p = -1) {
	par[u] = p;
	tree_sz[u] = 1;
	for(int v : tree[u]) {
		if(v == p) continue;
		depth[v] = depth[u]+1;
		dfs1(v, u);
		tree_sz[u] += tree_sz[v];
	}
}

int head[N];

void heavy_light(int u = 0, int p = -1) {
	ri[u] = t++;
	pair<int, int> mxch{-1, -1};
	for(int v : tree[u]) {
		if(v == p) continue;
		if(tree_sz[v] > mxch.second) {
			mxch = {v, tree_sz[v]};
		}
	}
	if(mxch.first == -1) return;
	head[mxch.first] = head[u];
	heavy_light(mxch.first, u);
	for(int v : tree[u]) {
		if(v == p || v == mxch.first) {
			continue;
		}
		head[v] = v;
		heavy_light(v, u);
	}
}

void tree_range_indices(int l, int r, vec<int>& res, int i = 1, int tl = 0, int tr = N) {
	if(tl >= r || tr <= l) return;
	if(tl >= l && tr <= r) {
		res.push_back(i);
		return;
	}
	int tm = (tl + tr)/2;
	tree_range_indices(l, r, res, i*2, tl, tm);
	tree_range_indices(l, r, res, i*2+1, tm, tr);
}

vec<int> range_indices(int u, int v) {
	vec<int> res = {};
	while(u != v) {
		if(head[u] == head[v]) {
			if(depth[u] > depth[v]) swap(u, v);
			tree_range_indices(ri[u]+1, ri[v]+1, res);
			break;
		}
		if(depth[head[u]] < depth[head[v]]) swap(u, v);
		if(head[u] == u) {
			tree_range_indices(ri[u], ri[u]+1, res);
			u = par[u];
		}
		else {
			tree_range_indices(ri[head[u]]+1, ri[u]+1, res);
			u = head[u];
		}
		//cerr << "STUCK 2" << '\n';
	}
	return res;
}

int32_t main() {
	int n, m, q;
	cin >> n >> m >> q;

	map<int, pair<int, int>> edges;

	for(int i = 0; i<n-1; i++) {
		int u, v;
		cin >> u >> v;
		u--;v--;
		tree[u].push_back(v);
		tree[v].push_back(u);

		edges.insert({i, {u, v}});
	}

	dfs1();
	heavy_light();

	for(int i = 0; i<m; i++) {
		int ei, c;
		cin >> ei >> c;
		ei--;
		auto [u, v] = edges[ei];
		if(depth[u] > depth[v]) swap(u, v);
		insert(ri[v], c);
	}

	for(int i = 0; i<q; i++) {
		int u, v, s, g;
		cin >> u >> v >> g >> s;
		u--; v--;
		vec<int> root_inds = range_indices(u, v);
		vec<Node*> nodes(root_inds.size());
		int tot_cnt = 0;
		for(int i = 0; i<root_inds.size(); i++) {
			nodes[i] = &roots[root_inds[i]];
			tot_cnt += nodes[i]->cnt;
		}
		int sum = 0;
		int cnt = 0;
		int l = 0;
		int r = CMX;
		while(l+1 != r) {
			int m = (l+r)/2;
			int cand_sum = sum;
			int cand_cnt = cnt;
			for(int i = 0; i<nodes.size(); i++) {
				cand_sum += nodes[i]->get_left()->sum;
				cand_cnt += nodes[i]->get_left()->cnt;
			}
			if(cand_sum <= s) {
				l = m;
				sum = cand_sum;
				cnt = cand_cnt;
				for(int i = 0; i<nodes.size(); i++) {
					nodes[i] = nodes[i]->get_right();
				}
			}
			else {
				r = m;
				for(int i = 0; i<nodes.size(); i++) {
					nodes[i] = nodes[i]->get_left();
				}
			}

			//cerr << "STUCK 1" << '\n';

		}
		int cur_cnt = 0;
		for(int i = 0; i<nodes.size(); i++) {
			cur_cnt += nodes[i]->cnt;
		}
		//cerr << "CURCNT: " << cur_cnt << '\n';

		cnt += min((s-sum)/l, cur_cnt);

		//cerr << tot_cnt << ' ' << cnt << ' ' << g << '\n';
		assert(sum <= s);
		if(g < tot_cnt-cnt) cout << -1 << endl;
		else cout << g-(tot_cnt-cnt) << endl;
	}
}

Compilation message (stderr)

currencies.cpp: In function 'int32_t main()':
currencies.cpp:171:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |   for(int i = 0; i<root_inds.size(); i++) {
      |                  ~^~~~~~~~~~~~~~~~~
currencies.cpp:183:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |    for(int i = 0; i<nodes.size(); i++) {
      |                   ~^~~~~~~~~~~~~
currencies.cpp:191:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |     for(int i = 0; i<nodes.size(); i++) {
      |                    ~^~~~~~~~~~~~~
currencies.cpp:197:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |     for(int i = 0; i<nodes.size(); i++) {
      |                    ~^~~~~~~~~~~~~
currencies.cpp:206:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |   for(int i = 0; i<nodes.size(); i++) {
      |                  ~^~~~~~~~~~~~~

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