Submission #878410

#	Time	Username	Problem	Language	Result	Execution time	Memory
878410		SanguineChameleon	Closing Time (IOI23_closing)	C++17	59 / 100	1024 ms	35684 KiB

closing

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

const long long inf = 1e18L + 20;

namespace cardboard {
	vector<pair<int, long long>> boxes;
	long long K;

	bool cmp(pair<int, int> p1, pair<int, int> p2) {
		return boxes[p1.second].second - boxes[p1.first].second > boxes[p2.second].second - boxes[p2.first].second;
	}

	namespace whole {
		struct half {
			set<int> ids;
			set<pair<long long, int>> ones;
			set<pair<long long, int>> twos;
			long long sum = 0;
			int cnt = 0;
			int side;

			half(int _side): side(_side) {};

			void clear() {
				ids.clear();
				ones.clear();
				twos.clear();
				sum = 0;
				cnt = 0;
			}

			void add(int id) {
				if (side == 1) {
					sum += boxes[id].second;
				}
				ids.insert(id);
				if (boxes[id].first == 1) {
					ones.emplace(boxes[id].second, id);
					cnt += 1;
				}
				else {
					twos.emplace(boxes[id].second, id);
					cnt += 2;
				}
			}

			void rem(int id) {
				if (side == 1) {
					sum -= boxes[id].second;
				}
				ids.erase(id);
				if (boxes[id].first == 1) {
					ones.erase({boxes[id].second, id});
					cnt -= 1;
				}
				else {
					twos.erase({boxes[id].second, id});
					cnt -= 2;
				}
			}
		} left_half(1), right_half(2);

		set<int> ids;

		void fix() {
			left_half.clear();
			right_half.clear();
			bool flag = false;
			for (auto id: ids) {
				if (!flag && left_half.sum + boxes[id].second <= K) {
					left_half.add(id);
				}
				else {
					flag = true;
					right_half.add(id);
				}
			}
		}

		void add(int id) {
			ids.insert(id);
			fix();
		}

		void rem(int id) {
			ids.erase(id);
			fix();
		}

		int get() {
			vector<long long> cur_dp = {0};
			for (auto id: ids) {
				vector<long long> nxt_dp = cur_dp;
				nxt_dp.resize(nxt_dp.size() + boxes[id].first, inf);
				for (int j = 0; j < (int)cur_dp.size(); j++) {
					nxt_dp[j + boxes[id].first] = min(nxt_dp[j + boxes[id].first], cur_dp[j] + boxes[id].second);
				}
				cur_dp.swap(nxt_dp);
			}
			for (int i = (int)cur_dp.size() - 1; i >= 0; i--) {
				if (cur_dp[i] <= K) {
					return i;
				}
			}
			return 0;
/*			int res = left_half.ids.size();
			if (!right_half.ones.empty() && left_half.sum + right_half.ones.begin()->first <= K) {
				res++;
			}
			else if (!left_half.ones.empty() && !right_half.twos.empty() && left_half.sum - left_half.ones.rbegin()->first + right_half.twos.begin()->first <= K) {
				res++;
			}
			return res;*/
		}
	}

	int solve(int N, long long _K, vector<pair<long long, long long>> costs) {
		K = _K;
		vector<pair<long long, int>> order(N << 1);
		for (int i = 0; i < N; i++) {
			order[i << 1] = {costs[i].first << 1, i << 1};
			order[i << 1 | 1] = {costs[i].second, i << 1 | 1};
		}
		sort(order.begin(), order.end());
		vector<pair<int, int>> ids(N);
		boxes.resize(N << 1);
		for (int i = 0; i < (N << 1); i++) {
			if (order[i].second & 1) {
				boxes[i] = {2, order[i].first};
				ids[order[i].second >> 1].second = i;
			}
			else {
				boxes[i] = {1, order[i].first >> 1};
				ids[order[i].second >> 1].first = i;
			}
		}
		sort(ids.begin(), ids.end(), cmp);
		whole::ids.clear();
		for (int i = 0; i < N; i++) {
			whole::add(ids[i].second);
		}
		int res = whole::get();
		for (int i = 0; i < N; i++) {
			whole::add(ids[i].first);
			whole::rem(ids[i].second);
			res = max(res, whole::get());
		}
		return res;
	}
}

namespace tree {
	vector<vector<pair<int, int>>> adj;

	void init(int N) {
		adj.resize(N);
		for (int i = 0; i < N; i++) {
			adj[i].clear();
		}
	}

	void add_edge(int u, int v, int w) {
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}

	void dfs(int u, int p, vector<long long> &dist) {
		for (auto [v, w]: adj[u]) {
			if (v != p) {
				dist[v] = dist[u] + w;
				dfs(v, u, dist);
			}
		}
	}
}

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
	tree::init(N);
	for (int i = 0; i < N - 1; i++) {
		tree::add_edge(U[i], V[i], W[i]);
	}
	vector<long long> distX(N), distY(N);
	tree::dfs(X, -1, distX);
	tree::dfs(Y, -1, distY);
	vector<long long> dists(distX.begin(), distX.end());
	dists.insert(dists.end(), distY.begin(), distY.end());
	sort(dists.begin(), dists.end());
	int res = 0;
	long long sum = 0;
	for (auto d: dists) {
		if (sum + d <= K) {
			sum += d;
			res++;
		}
		else {
			break;
		}
	}
	int cnt = 0;
	vector<pair<long long, long long>> costs(N);
	for (int i = 0; i < N; i++) {
		if (distX[i] + distY[i] == distX[Y]) {
			cnt++;
			K -= min(distX[i], distY[i]);
			costs[i] = {max(distX[i], distY[i]) - min(distX[i], distY[i]), inf};
		}
		else {
			costs[i] = {min(distX[i], distY[i]), max(distX[i], distY[i])};
		}
	}
	if (K >= 0) {
		res = max(res, cnt + cardboard::solve(N, K, costs));
	}
	return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17