Submission #277050

#	Time	Username	Problem	Language	Result	Execution time	Memory
277050		tjd229	City Mapping (NOI18_citymapping)	C++14	0 / 100	2086 ms	4608 KiB

citymapping

#include "citymapping.h"
#include <vector>
#include <algorithm>
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
using namespace std;
vector<pii > edge[1001];
int sz[1001],p[1001];
ll d[1001][1001];
int dfs(int x) {
	if (edge[x].empty()) return x;
	int mx = 0;
	int nxt= 0;
	for (auto p : edge[x]) {
		int c = p.first;
		if (mx < sz[c]) {
			nxt = c;
			mx = sz[c];
		}
	}
	return dfs(nxt);
}
int find_par(int root,int x,ll dist) {
	if (edge[root].empty()) return root;

	int leaf = dfs(root);
	ll x2l = get_distance(x, leaf);
	int lca = leaf;
	while (d[root][leaf] + d[root][x] < (d[root][lca] << 1) + x2l)
		lca = p[lca];

	if (edge[lca].size() <= 1) return lca;
	//2
	int l = edge[lca][0].first, r = edge[lca][1].first;
	if (sz[l] < sz[r]) return find_par(l, x, dist - d[root][l]);
	else return find_par(r, x, dist - d[root][r]);
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
	vector<pli > v;
	for (int i = 2; i <= N; ++i) {
		d[1][i] = d[i][1] = get_distance(1, i);
		v.push_back({ d[1][i],i });
	}
	sort(v.begin(), v.end());
	sz[1] = 1;
	for (auto pr : v) {
		int x = pr.second;
		ll dist = pr.first;
		int par = find_par(1, x, dist);
		edge[par].push_back({ x,dist - d[par][1] });
		p[x] = par;
		while (x) {
			++sz[x];
			d[p[x]][x] = d[x][p[x]] = d[1][x] - d[1][p[x]];
			x = p[x];
		}
	}
	int len = 0;
	for (int i = 1; i <= N; ++i) {
		for (auto p : edge[i]) {
			A[len] = i;
			B[len] = p.first;
			W[len] = p.second;
			++len;
		}
	}
}

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