oj.uz

Submission #878404

# Submission time Handle Problem Language Result Execution time Memory
878404 2023-11-24T10:11:02 Z SanguineChameleon Closing Time (IOI23_closing) C++17
26 / 100
 128 ms 35124 KB 
#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);
		for (int i = 0; i < N; i++) {
			whole::add(ids[i].second);
		}
		int res = whole::get();
		for (int i = 0; i < N; i++) {
			assert(whole::ids.count(ids[i].first) ^ whole::ids.count(ids[i].second));
		}
		for (int i = 0; i < N; i++) {
			whole::add(ids[i].first);
			whole::rem(ids[i].second);
			for (int i = 0; i < N; i++) {
				assert(whole::ids.count(ids[i].first) ^ whole::ids.count(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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 30940 KB Output is correct
2 Correct 128 ms 35124 KB Output is correct
3 Correct 66 ms 2900 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 5 ms 348 KB Output is correct
14 Correct 4 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Runtime error 1 ms 604 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 5 ms 348 KB Output is correct
14 Correct 4 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Runtime error 1 ms 604 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 388 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 424 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Correct 4 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 388 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 424 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Runtime error 1 ms 600 KB Execution killed with signal 6
38 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Correct 4 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Runtime error 1 ms 604 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Correct 4 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Runtime error 1 ms 604 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Correct 4 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Runtime error 1 ms 604 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -