Submission #832629

#	Time	Username	Problem	Language	Result	Execution time	Memory
832629		pavement	Wiring (IOI17_wiring)	C++17	0 / 100	1078 ms	8300 KiB

wiring

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

#define eb emplace_back
#define mp make_pair

using ll = long long;
using ii = pair<int, int>;

ll min_total_length(vector<int> _r, vector<int> _b) {
	int n = (int)_r.size(), m = (int)_b.size();
	ll ans = 0;
	vector<ii> r, b;
	for (int i = 0; i < n; i++) {
		r.eb(_r[i], 0);
	}
	for (int i = 0; i < m; i++) {
		b.eb(_b[i], 1);
	}
	vector<ii> g;
	merge(r.begin(), r.end(), b.begin(), b.end(), back_inserter(g));
	vector<bool> is_host(n + m, 0), can_remove(n + m, 1);
	vector<ll> conn_len(n + m, 0), host(n + m, -1), cnt_host(n + m, 0);
	int ptr = -1;
	for (int i = 1; i < n + m; i++) {
		if (g[i].second != g[i - 1].second) {
			for (int j = i - 1; j >= 0; j--) {
				conn_len[j] = g[i].first - g[j].first;
				host[j] = i;
				cnt_host[i]++;
			}
			if (i == 1) {
				can_remove[i] = 0;
			}
			is_host[i] = 1;
			ptr = i;
			break;
		}
	}
	assert(ptr != -1);
	for (int i = ptr + 1; i < n + m; i++) {
		pair<ll, int> case_1 = mp((ll)1e16, -1), case_2 = mp((ll)1e16, -1);
		for (int j = 0; j < i; j++) {
			if (g[j].second == g[i].second) {
				continue;
			}
			if (!is_host[j]) {
				case_1 = min(case_1, mp((ll)g[i].first - g[j].first - (can_remove[host[j]] ? conn_len[j] : 0), j));
			} else {
				case_2 = min(case_2, mp((ll)g[i].first - g[j].first, j));
			}
		}
		if (case_1.first < case_2.first) {
			cnt_host[host[case_1.second]]--;
			if (cnt_host[host[case_1.second]] == 1) {
				can_remove[host[case_1.second]] = 0;
			} else if (cnt_host[host[case_1.second]] == 0) {
				assert(can_remove[host[case_1.second]] == 0);
				host[host[case_1.second]] = case_1.second;
				is_host[host[case_1.second]] = 0;
				cnt_host[host[case_1.second]] = 0;
				conn_len[host[case_1.second]] = conn_len[case_1.second];
				cnt_host[case_1.second] = 1;
				host[case_1.second] = -1;
			}
			is_host[case_1.second] = 1;
			conn_len[case_1.second] = 0;
			host[i] = case_1.second;
			cnt_host[case_1.second]++;
			can_remove[case_1.second] = cnt_host[case_1.second] > 1;
			conn_len[i] = g[i].first - g[case_1.second].first;
		} else {
			host[i] = case_2.second;
			cnt_host[case_2.second]++;
			assert(cnt_host[case_2.second] > 1);
			can_remove[case_2.second] = 1;
			conn_len[i] = case_2.first;
		}
	}
	for (int i = 0; i < n + m; i++) {
		ans += conn_len[i];
	}
	return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45