Submission #972928

#	Time	Username	Problem	Language	Result	Execution time	Memory
972928		NoMercy	City Mapping (NOI18_citymapping)	C++17	57 / 100	8 ms	856 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	vector<pair<ll , int>> v;
	v.push_back({0LL , 1});
	for (int i = 2;i <= N;i ++) {
		ll w = get_distance(1 , i);
		v.push_back({w , i});
	}
	sort(v.begin() , v.end());
	int ind = 0;
	for (int i = 1;i < N;i ++) {
		if (ind == N - 1) {
			break;
		}
		for (int j = i - 1;j >= 0;j --) {
			ll w = v[i].first - v[j].first;
			if (j >= 1) {
				w = get_distance(v[i].second , v[j].second);
			}
			if (w == v[i].first - v[j].first) {
				A[ind] = min(v[i].second , v[j].second);
				B[ind] = max(v[i].second , v[j].second);
				W[ind] = w;
				ind ++;
				break;
			}
		}
	}
	return;
}
/*

5 50000 5
1 4 8
2 4 1
3 4 7
3 5 3

*/

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