Submission #963859

#	Time	Username	Problem	Language	Result	Execution time	Memory
963859		guechotjrhh	City Mapping (NOI18_citymapping)	C++14	32 / 100	2 ms	604 KiB

citymapping

#include "citymapping.h"
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
#define pi pair<ll,ll>
#define x first
#define y second
void find_roads(int N, int Q, int A[], int B[], int W[]) {
	ll u = 0, mi = 1;
	for (int i = 2; i <= N; i++) {
		ll x = get_distance(1, i);
		if (x > u) {
			u = x;
			mi = i;
		}
	}
	vector<pi> vec;
	for (int i = 1; i <= N; i++) {
		if (i != mi) vec.push_back({ get_distance(mi,i),i });
	}
	sort(vec.begin(), vec.end());
	A[0] = mi; B[0] = vec[0].y; W[0] = vec[0].x;
	for (int i = 1; i < N-1; i++) {
		A[i] = vec[i].y; B[i] = vec[i - 1].y; W[i] = vec[i].x - vec[i - 1].x;
	}
	return;
}
/*
5 500000 1
1 4 8
4 2 1
4 3 7
3 5 3
*/

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 0 / 43