Submission #1024443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024443		thinknoexit	City Mapping (NOI18_citymapping)	C++17	32 / 100	2 ms	8284 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1010;
ll dis[N][N];
int n;
ll d(int i, int j) {
	if (i == j) return 0;
	if (!dis[i][j]) return dis[i][j] = dis[j][i] = get_distance(i, j);
	return dis[i][j];
}
void find_roads(int NN, int Q, int A[], int B[], int W[]) {
	n = NN;
	ll mx = 0;
	int idx = 0;
	for (int i = 2;i <= n;i++) {
		if (d(1, i) > mx) {
			mx = d(1, i);
			idx = i;
		}
	}
	vector<pair<ll, int>> v;
	for (int i = 1;i <= n;i++) {
		v.push_back({ d(idx, i), i });
	}
	sort(v.begin(), v.end());
	for (int i = 1;i < n;i++) {
		A[i - 1] = v[i - 1].second;
		B[i - 1] = v[i].second;
		W[i - 1] = v[i].first - v[i - 1].first;
	}
	return;
}

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