Submission #580741

#	Time	Username	Problem	Language	Result	Execution time	Memory
580741		ntabc05101	City Mapping (NOI18_citymapping)	C++14	100 / 100	19 ms	8416 KiB

citymapping

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

using namespace std;

const int mxN = 1000;

long long dst[mxN][mxN];

long long get_dst(int x, int y) {
	if (x > y) {
		swap(x, y);
	}
	auto &ret = dst[x][y];
	if (~ret) {
		return ret;
	}
	return ret = get_distance(x + 1, y + 1);
}

long long &dist(int x, int y) {
	if (x > y) {
		swap(x, y);
	}
	return dst[x][y];
}

int sz[mxN], Cnt;
vector<pair<int, int>> chd[mxN];
bool used[mxN];

void dfs0(int u, int r) {
	sz[u] = 1;
	Cnt++;
	for (auto &to: chd[u]) {
		if (!used[to.first]) {
			dist(r, to.first) = dist(r, u) + to.second;
			dfs0(to.first, r);
			sz[u] += sz[to.first];
		}
	}
}

vector<pair<int, int>> lst;

int dfs1(int u) {
	pair<int, int> mx = {-1, -1};
	for (auto &to: chd[u]) {
		if (!used[to.first] && (mx.first == -1 || sz[mx.first] < sz[to.first])) {
			mx = to;
		}
	}
	if (~mx.first) {
		lst.push_back(mx);
		return dfs1(mx.first);
	}
	return u;
}

void find_roads(int n, int q, int a[], int b[], int w[]) {
	/*a[0] = 2; a[1] = 4; a[2] = 4; a[3] = 5;
	b[0] = 4; b[1] = 1; b[2] = 2; b[3] = 3;
	w[0] = 7; w[1] = 8; w[2] = 1; w[3] = 3;
	return ;*/

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dst[i][j] = -1;
		}
	}
	for (int i = 0; i < n; i++) {
		dist(i, i) = 0;
	}

	vector<pair<long long, int>> ds;
	for (int i = 1; i < n; i++) {
		ds.push_back({get_dst(0, i), i});
		//cerr << ds.back().first << " " << ds.back().second << "\n";
	}

	sort(ds.begin(), ds.end());
	int m = 0;
	for (auto &x: ds) {
		int r = 0;
			/*for (int i = 0; i < n; i++) {
				cerr << dist(r, i) << "\n";
			}*/
	
		while (true) {
			Cnt = 0;
			dfs0(r, r);
			if (Cnt == 1) {
				break;
			}
			int l = dfs1(r);
			long long xl = get_dst(x.second, l), rm = (get_dst(r, x.second) + get_dst(r, l) - xl) / 2;
			for (auto &y: lst) {
				used[y.first] = 1;
			}
			int i = 0;
			// cerr << r << " " << get_dst(r, x.second) << " " << get_dst(r, l) << " " << xl << " " << rm;
			while (rm > 0) {
				rm -= lst[i++].second;
			}
			int M = (i ? lst[i - 1].first: r);
			// cerr << " " << l << " " << x.second << " " << M << "\n";
		dist(M, x.second) = (get_dst(r, x.second) + get_dst(l, x.second) - get_dst(r, l)) / 2;
			lst.clear();
			r = M;
		}
		a[m] = 1 + r; b[m] = 1 + x.second; w[m] = dist(r, x.second);
		// cerr << " " << a[m] << " " << b[m] << " " << w[m] << "\n";
		chd[r].push_back({b[m] - 1, w[m]});
		dist(r, b[m] - 1) = w[m];
		m++;
		for (int i = 0; i < n; i++) {
			used[i] = 0;
		}
	}

}

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