oj.uz

Submission #832612

# Submission time Handle Problem Language Result Execution time Memory
832612 2023-08-21T12:37:07 Z pavement Wiring (IOI17_wiring) C++17
0 / 100
 1000 ms 7492 KB 
#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), can_remove(n + m, 1);
	vector<int> conn_len(n + m), host(n + m), cnt_host(n + m);
	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) {
				host[host[case_1.second]] = case_1.second;
				is_host[host[case_1.second]] = 0;
				conn_len[host[case_1.second]] = llabs(g[case_1.second].first - g[host[case_1.second]].first);
				cnt_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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 296 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14694'
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 1066 ms 7492 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '17703', found: '18722'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '27', found: '30'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 296 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14694'
3 Halted 0 ms 0 KB -