Submission #1123262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123262		Gervid	Road Construction (JOI21_road_construction)	C++20	6 / 100	843 ms	23132 KiB

road_construction

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <array>

using namespace std;

const unsigned int max_num_of_distances = 3000000;

struct point
{
	int x, y;
};

struct scp
{
	int id, next;
	long long dis;

	const bool operator< (const scp other) const
	{
		return dis < other.dis;
	}
	const bool operator> (const scp other) const
	{
		return dis > other.dis;
	}
};

int main()
{
	iostream::sync_with_stdio(0);
	cin.tie(0);

	int n, k, i;
	cin >> n >> k;

	vector<point> p(n);
	for (i = 0; i < n; i++)
	{
		cin >> p[i].x >> p[i].y;
	}

	vector<pair<long long, point>> scalars;

	for (i = 0; i < n; i++)
	{
		long long xi = static_cast<long long>(p[i].x) + 2000000000LL;
		long long yi = static_cast<long long>(p[i].y) + 2000000000LL;
		long long dot_product = xi + yi;
		scalars.push_back({ dot_product, p[i] });
	}

	sort(scalars.begin(), scalars.end(), [](pair<long long, point> a, pair<long long, point> b) {return a.first < b.first; });

	vector<int> distances;
	distances.reserve(max_num_of_distances);
	priority_queue<scp, vector<scp>, greater<scp>> q;

	for (i = 0; i < n-1; i++)
	{
		q.push({ i, i + 1, scalars[i+1].first - scalars[i].first});
	}
	while (distances.size() < max_num_of_distances && !q.empty())
	{
		int next = q.top().next, id = q.top().id;
		q.pop();

		distances.push_back(abs(scalars[id].second.x - scalars[next].second.x) + abs(scalars[id].second.y - scalars[next].second.y));
		if (next+1 < n) q.push({ id, next + 1, scalars[next + 1].first - scalars[id].first });
	}

	sort(distances.begin(), distances.end());

	for (i = 0; i < k; i++)
	{
		cout << distances[i] << '\n';
	}
}

//11 10
//10 -8
//7 2
//7 -8
//-3 -6
//-2 1
//-8 6
//8 -1
//2 4
//6 -6
//2 -1
//-10000 20000

• Subtask 1: 0 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35