Submission #1024581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024581		thinknoexit	City Mapping (NOI18_citymapping)	C++17	32 / 100	3 ms	8540 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1010;
int n;
ll dis[N][N];
int A[N], B[N], W[N], tot;
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 play(vector<int>& v, int U) {
	int m = v.size();
	if (m == 1) return;
	int V = 0;
	ll mx = 0;
	for (int j = 0;j < m;j++) {
		if (d(U, v[j]) > mx) {
			mx = d(U, v[j]);
			V = v[j];
		}
	}
	// U, V is leaf
	ll all = d(U, V);
	vector<pair<ll, int>> in, rem;
	for (int j = 0;j < m;j++) {
		if (d(U, v[j]) + d(v[j], V) == all) {
			in.push_back({ d(U, v[j]), v[j] });
		}
		else {
			ll extra = (d(U, v[j]) + d(v[j], V) - all) / 2;
			rem.push_back({ d(U, v[j]) - extra, v[j] });
		}
	}
	sort(in.begin(), in.end());
	sort(rem.begin(), rem.end());
	vector<vector<int>> r;
	vector<int> leaf;
	int p = 0;
	for (int i = 1;i < (int)in.size();i++) {
		A[tot] = in[i - 1].second;
		B[tot] = in[i].second;
		W[tot] = in[i].first - in[i - 1].first;
		tot++;
		vector<int> nw;
		ll mn = LLONG_MAX;
		int idx = 0;
		while (p < (int)rem.size() && rem[p].first == in[i].first) {
			int vl = rem[p].second;
			ll extra = (d(U, vl) + d(vl, V) - all) / 2;
			if (extra < mn) {
				mn = extra;
				idx = vl;
			}
			nw.push_back(vl);
			p++;
		}
		if (!nw.empty()) {
			A[tot] = idx;
			B[tot] = in[i].second;
			W[tot] = mn;
			tot++;
			r.push_back(nw);
			leaf.push_back(idx);
		}
	}
	for (int i = 0;i < (int)r.size();i++) {
		play(r[i], leaf[i]);
	}
}
void find_roads(int NN, int Q, int A[], int B[], int W[]) {
	n = NN;
	vector<int> init(n);
	iota(init.begin(), init.end(), 1);
	int leaf = 0;
	ll mx = 0;
	for (int i = 2;i <= n;i++) {
		if (d(1, i) > mx) {
			mx = d(1, i);
			leaf = i;
		}
	}
	play(init, leaf);
	for (int i = 0;i < n - 1;i++) {
		A[i] = ::A[i];
		B[i] = ::B[i];
		W[i] = ::W[i];
		//cout << A[i] << ' ' << B[i] << ' ' << W[i] << '\n';
	}
	return;
}

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